Submission #3235329
Source Code Expand
//毒瘤! #include<iostream> #include<cstdio> #include<cstring> #include<vector> #define maxn 1005 #define maxm 200005 using namespace std; inline int qread(){ int x=0,sign=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') sign=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } return x*sign; } int n,m; int s[maxm],e[maxm]; vector<int>E[maxn]; void add_edge(int u,int v){ E[u].push_back(v); } int used[maxn]; int route[maxn][maxn]; void dfs(int s,int x){ int y; used[x]=1; route[s][x]++; int cnt=E[x].size(); for(int i=0;i<cnt;i++){ y=E[x][i]; if(y==s) continue; if(!used[y]&&route[s][y]<2){ dfs(s,y); } } } int judge(int u,int v){//1为diff,0为same if(route[v][u]>0){//在一个SCC中 if(route[u][v]>=2) return 0; else return 1; }else{//不在一个SCC中 if(route[u][v]>=2) return 1; else return 0; } } char a[]="same",b[]="diff"; void qprint(char *s,int len){ for(int i=0;i<len;i++){ putchar(s[i]); } putchar('\n'); } int main(){ // scanf("%d %d",&n,&m); n=qread(); m=qread(); int u,v; for(int i=1;i<=m;i++){ // scanf("%d %d",&u,&v); s[i]=qread(); e[i]=qread(); add_edge(s[i],e[i]); } int y; for(int i=1;i<=n;i++){ int cnt=E[i].size(); for(int j=0;j<cnt;j++){ y=E[i][j]; if(route[i][y]<2){ memset(used,0,sizeof(used)); dfs(i,y); } } } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++){ // printf("%d ",route[i][j]); // } // printf("\n"); // } for(int i=1;i<=m;i++){ if(judge(s[i],e[i]) )qprint(b,4); else qprint(a,4); } }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Edges |
User | vjudge4 |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 1557 Byte |
Status | AC |
Exec Time | 997 ms |
Memory | 8320 KB |
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 | 532 ms | 7936 KB |
bigcycle_1 | AC | 530 ms | 7936 KB |
dag_0 | AC | 233 ms | 5888 KB |
dag_1 | AC | 460 ms | 7936 KB |
dag_2 | AC | 275 ms | 5888 KB |
dag_3 | AC | 508 ms | 7936 KB |
dag_4 | AC | 420 ms | 7424 KB |
dag_5 | AC | 460 ms | 7936 KB |
dag_6 | AC | 407 ms | 7168 KB |
dag_7 | AC | 506 ms | 7936 KB |
dagex2_0 | AC | 434 ms | 7552 KB |
dagex2_1 | AC | 474 ms | 7936 KB |
dagex2_2 | AC | 454 ms | 7552 KB |
dagex2_3 | AC | 477 ms | 7936 KB |
dagex_0 | AC | 402 ms | 7424 KB |
dagex_1 | AC | 480 ms | 7936 KB |
dagex_2 | AC | 397 ms | 7168 KB |
dagex_3 | AC | 488 ms | 7936 KB |
example_0 | AC | 1 ms | 2304 KB |
example_1 | AC | 2 ms | 2304 KB |
example_2 | AC | 2 ms | 2304 KB |
maxrand_0 | AC | 522 ms | 7936 KB |
maxrand_1 | AC | 522 ms | 7936 KB |
sep2_0 | AC | 528 ms | 7936 KB |
sep2_1 | AC | 534 ms | 7936 KB |
sep2ex_0 | AC | 401 ms | 8064 KB |
sep2ex_1 | AC | 403 ms | 8064 KB |
sep2ex_2 | AC | 527 ms | 7936 KB |
sep2ex_3 | AC | 536 ms | 7936 KB |
sep2ex_4 | AC | 741 ms | 8320 KB |
sep2ex_5 | AC | 723 ms | 8192 KB |
sep2ex_6 | AC | 931 ms | 7936 KB |
sep2ex_7 | AC | 934 ms | 7936 KB |
sep2ex_8 | AC | 991 ms | 7808 KB |
sep2ex_9 | AC | 997 ms | 7808 KB |
smallrand_0 | AC | 1 ms | 2304 KB |
smallrand_1 | AC | 2 ms | 2304 KB |
smallrand_2 | AC | 1 ms | 2304 KB |
smallrand_3 | AC | 2 ms | 2304 KB |
smallrand_4 | AC | 1 ms | 2304 KB |
smallrand_5 | AC | 2 ms | 2432 KB |
smallrand_6 | AC | 1 ms | 2304 KB |
smallrand_7 | AC | 1 ms | 2304 KB |
smallrand_8 | AC | 2 ms | 2304 KB |
smallrand_9 | AC | 2 ms | 2304 KB |
sparserand_0 | AC | 82 ms | 4608 KB |
sparserand_1 | AC | 83 ms | 4608 KB |
worst2_0 | AC | 45 ms | 7168 KB |
worst2_1 | AC | 56 ms | 7296 KB |
worst2_2 | AC | 48 ms | 6912 KB |
worst2_3 | AC | 54 ms | 7168 KB |
worst_0 | AC | 181 ms | 8064 KB |
worst_1 | AC | 240 ms | 8192 KB |
worst_2 | AC | 81 ms | 7424 KB |
worst_3 | AC | 119 ms | 7424 KB |