Submission #3234170
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
void File(){
freopen("ARC92F.in","r",stdin);
freopen("ARC92F.out","w",stdout);
}
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
#define mem(a) memset(a,0,sizeof(a))
const int maxn=1000+10;
const int maxm=200000+10;
vector<int>E[maxn];
int n,m,beg[maxn],len,num[maxn][maxn];
bool can[maxn][maxn],vis[maxn],can1[maxn][maxn];
int vis1[maxn],vis2[maxn],from[maxm],to[maxm];
void dfs(int u,int rt){
vis[u]=1;
can[rt][u]=1;
int size=E[u].size()-1;
REP(i,0,size){
int v=E[u][i];
if(vis[v])continue;
dfs(v,rt);
}
}
void dfs1(int u){
vis[u]=1;
int size=E[u].size()-1;
REP(i,0,size){
int v=E[u][i];
if(vis[v])continue;
vis1[v]=num[u][v];
dfs1(v);
}
}
void dfs2(int u){
vis[u]=1;
int size=E[u].size()-1;
DREP(i,size,0){
int v=E[u][i];
if(vis[v])continue;
vis2[v]=num[u][v];
dfs2(v);
}
}
int main(){
//File();
scanf("%d%d",&n,&m);
REP(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
E[u].push_back(v);
num[u][v]=++len;
from[len]=u;
to[len]=v;
}
REP(i,1,n){
dfs(i,i);
mem(vis);
}
REP(i,1,n){
dfs1(i);
mem(vis);
dfs2(i);
mem(vis);
int size=E[i].size()-1;
REP(j,0,size){
int v=E[i][j];
if(vis1[v]!=num[i][v] || vis2[v]!=num[i][v])
can1[i][v]=1;
}
mem(vis1);
mem(vis2);
}
REP(i,1,m){
int u=from[i],v=to[i];
if((can[v][u]^can1[u][v])==0)
puts("same");
else puts("diff");
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Two Faced Edges |
User |
vjudge3 |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
1760 Byte |
Status |
AC |
Exec Time |
708 ms |
Memory |
10240 KB |
Compile Error
./Main.cpp: In function ‘void File()’:
./Main.cpp:4:35: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("ARC92F.in","r",stdin);
^
./Main.cpp:5:37: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("ARC92F.out","w",stdout);
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:48:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:51:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1100 / 1100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example_0, example_1, example_2 |
All |
bigcycle_0, bigcycle_1, dag_0, dag_1, dag_2, dag_3, dag_4, dag_5, dag_6, dag_7, dagex2_0, dagex2_1, dagex2_2, dagex2_3, dagex_0, dagex_1, dagex_2, dagex_3, example_0, example_1, example_2, maxrand_0, maxrand_1, sep2_0, sep2_1, sep2ex_0, sep2ex_1, sep2ex_2, sep2ex_3, sep2ex_4, sep2ex_5, sep2ex_6, sep2ex_7, sep2ex_8, sep2ex_9, smallrand_0, smallrand_1, smallrand_2, smallrand_3, smallrand_4, smallrand_5, smallrand_6, smallrand_7, smallrand_8, smallrand_9, sparserand_0, sparserand_1, worst2_0, worst2_1, worst2_2, worst2_3, worst_0, worst_1, worst_2, worst_3 |
Case Name |
Status |
Exec Time |
Memory |
bigcycle_0 |
AC |
708 ms |
9856 KB |
bigcycle_1 |
AC |
694 ms |
9856 KB |
dag_0 |
AC |
173 ms |
7936 KB |
dag_1 |
AC |
314 ms |
9984 KB |
dag_2 |
AC |
357 ms |
8064 KB |
dag_3 |
AC |
649 ms |
9984 KB |
dag_4 |
AC |
282 ms |
9472 KB |
dag_5 |
AC |
305 ms |
9984 KB |
dag_6 |
AC |
519 ms |
9216 KB |
dag_7 |
AC |
645 ms |
9984 KB |
dagex2_0 |
AC |
293 ms |
9472 KB |
dagex2_1 |
AC |
313 ms |
9984 KB |
dagex2_2 |
AC |
294 ms |
9600 KB |
dagex2_3 |
AC |
310 ms |
9984 KB |
dagex_0 |
AC |
274 ms |
9344 KB |
dagex_1 |
AC |
309 ms |
9984 KB |
dagex_2 |
AC |
267 ms |
9216 KB |
dagex_3 |
AC |
312 ms |
9856 KB |
example_0 |
AC |
2 ms |
2304 KB |
example_1 |
AC |
2 ms |
2304 KB |
example_2 |
AC |
2 ms |
2304 KB |
maxrand_0 |
AC |
690 ms |
9856 KB |
maxrand_1 |
AC |
693 ms |
9856 KB |
sep2_0 |
AC |
692 ms |
9856 KB |
sep2_1 |
AC |
700 ms |
9856 KB |
sep2ex_0 |
AC |
503 ms |
10112 KB |
sep2ex_1 |
AC |
508 ms |
10112 KB |
sep2ex_2 |
AC |
444 ms |
9856 KB |
sep2ex_3 |
AC |
442 ms |
9856 KB |
sep2ex_4 |
AC |
490 ms |
10240 KB |
sep2ex_5 |
AC |
486 ms |
10240 KB |
sep2ex_6 |
AC |
550 ms |
9856 KB |
sep2ex_7 |
AC |
566 ms |
9856 KB |
sep2ex_8 |
AC |
642 ms |
9728 KB |
sep2ex_9 |
AC |
637 ms |
9856 KB |
smallrand_0 |
AC |
2 ms |
2304 KB |
smallrand_1 |
AC |
2 ms |
2304 KB |
smallrand_2 |
AC |
2 ms |
2304 KB |
smallrand_3 |
AC |
2 ms |
2304 KB |
smallrand_4 |
AC |
2 ms |
2304 KB |
smallrand_5 |
AC |
2 ms |
2304 KB |
smallrand_6 |
AC |
2 ms |
2304 KB |
smallrand_7 |
AC |
2 ms |
2304 KB |
smallrand_8 |
AC |
2 ms |
2304 KB |
smallrand_9 |
AC |
2 ms |
2304 KB |
sparserand_0 |
AC |
109 ms |
6528 KB |
sparserand_1 |
AC |
108 ms |
6528 KB |
worst2_0 |
AC |
45 ms |
8960 KB |
worst2_1 |
AC |
73 ms |
9472 KB |
worst2_2 |
AC |
43 ms |
8832 KB |
worst2_3 |
AC |
68 ms |
9216 KB |
worst_0 |
AC |
276 ms |
10112 KB |
worst_1 |
AC |
318 ms |
10240 KB |
worst_2 |
AC |
119 ms |
9344 KB |
worst_3 |
AC |
155 ms |
9600 KB |