Submission #3234513
Source Code Expand
//save code #include <iostream> #include <stdio.h> #include <string.h> #include <utility> #include <set> using namespace std; void read(int &x) { char ch=getchar();bool f=0;x=0; while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} if(f)x=-x; } void read(long long &x) { char ch=getchar();bool f=0;x=0; while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} if(f)x=-x; } struct graph_t { int front,nex; }graph[201001],graph2[201001],graph3[201001]; int tail=1000,tail2=1000,tail3=1000; void addedge(int u,int v) { int tmp=graph[u].nex; graph[u].nex=++tail; graph[tail].front=v; graph[tail].nex=tmp; } void addedge2(int u,int v) { int tmp=graph2[u].nex; graph2[u].nex=++tail2; graph2[tail2].front=v; graph2[tail2].nex=tmp; } void addedge3(int u,int v) { int tmp=graph3[u].nex; graph3[u].nex=++tail3; graph3[tail3].front=v; graph3[tail3].nex=tmp; } int vis[1001]; pair<int,int> edge[200001]; int nfinish=0; int finish[1001]; int nconnect=0; int connect[1001]; int indegree[1001],outdegree[1001]; int cnt[1001][1001]; void dfs1(int now) { vis[now]=1; for(int i=graph[now].nex;i;i=graph[i].nex) { if(vis[graph[i].front]!=1) { dfs1(graph[i].front); } } finish[nfinish++]=now; } void dfs2(int now) { // printf("dfs2(%d)\n",now); vis[now]=2; connect[now]=nconnect; for(int i=graph2[now].nex;i;i=graph2[i].nex) { if(vis[graph2[i].front]!=2) { dfs2(graph2[i].front); } } } void dfs3(int from,int now) { //vis[now]=3+from; for(int i=graph3[now].nex;i;i=graph3[i].nex) { if(cnt[from][graph3[i].front]>1)continue; //if(vis[now]==3+from)continue; cnt[from][graph3[i].front]+=cnt[from][now]; dfs3(from,graph3[i].front); } } int main() { int n,m; read(n);read(m); for(int i=0;i<m;i++) { int from,to; read(from);read(to); addedge(from,to); addedge2(to,from); edge[i]=make_pair(from,to); } for(int i=1;i<=n;i++) { if(vis[i]!=1)dfs1(i); } for(int i=nfinish-1;i>=0;i--) { if(vis[finish[i]]!=2) { nconnect++; dfs2(finish[i]); } } /* for(int i=1;i<=n;i++) { cout<<connect[i]<<" "; } cout<<endl;*/ for(int i=1;i<=n;i++) { for(int j=graph[i].nex;j;j=graph[j].nex) { if(connect[i]==connect[graph[j].front]) { outdegree[i]++; } } for(int j=graph2[i].nex;j;j=graph2[j].nex) { if(connect[i]==connect[graph2[j].front]) { indegree[i]++; } } } /* for(int i=1;i<=n;i++) { printf("in:%d,out:%d\n",indegree[i],outdegree[i]); }*/ for(int i=0;i<m;i++) { int from=edge[i].first,to=edge[i].second; if(connect[from]!=connect[to])addedge3(connect[from],connect[to]); } for(int i=1;i<=nconnect;i++) { cnt[i][i]=1; dfs3(i,i); } /* for(int i=1;i<=nconnect;i++) { for(int j=1;j<=nconnect;j++) { cout<<cnt[i][j]; } cout<<endl; }*/ for(int i=0;i<m;i++) { int from=edge[i].first,to=edge[i].second; if(connect[from]==connect[to]) { if(indegree[to]==1||outdegree[from]==1) { puts("diff"); } else { puts("same"); } } else { if(cnt[connect[from]][connect[to]]>1) { puts("diff"); } else { puts("same"); } } } return 0; } /* 3 3 1 2 1 3 2 3 2 2 1 2 2 1 */
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Edges |
User | vjudge1 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3259 Byte |
Status | WA |
Exec Time | 1686 ms |
Memory | 11520 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 37 ms | 9472 KB |
bigcycle_1 | AC | 37 ms | 9472 KB |
dag_0 | AC | 706 ms | 9600 KB |
dag_1 | AC | 1686 ms | 11520 KB |
dag_2 | AC | 17 ms | 7680 KB |
dag_3 | AC | 35 ms | 9472 KB |
dag_4 | AC | 1486 ms | 10880 KB |
dag_5 | AC | 1679 ms | 11392 KB |
dag_6 | WA | 27 ms | 8576 KB |
dag_7 | AC | 34 ms | 9472 KB |
dagex2_0 | AC | 970 ms | 11008 KB |
dagex2_1 | AC | 1085 ms | 11392 KB |
dagex2_2 | AC | 481 ms | 10112 KB |
dagex2_3 | AC | 524 ms | 10496 KB |
dagex_0 | AC | 890 ms | 10880 KB |
dagex_1 | AC | 1073 ms | 11392 KB |
dagex_2 | AC | 357 ms | 9600 KB |
dagex_3 | AC | 476 ms | 10368 KB |
example_0 | AC | 2 ms | 6400 KB |
example_1 | AC | 2 ms | 6400 KB |
example_2 | AC | 2 ms | 6400 KB |
maxrand_0 | AC | 37 ms | 9472 KB |
maxrand_1 | AC | 35 ms | 9472 KB |
sep2_0 | WA | 34 ms | 9472 KB |
sep2_1 | WA | 34 ms | 9472 KB |
sep2ex_0 | AC | 36 ms | 9472 KB |
sep2ex_1 | AC | 39 ms | 9472 KB |
sep2ex_2 | AC | 36 ms | 9472 KB |
sep2ex_3 | AC | 36 ms | 9472 KB |
sep2ex_4 | AC | 40 ms | 9344 KB |
sep2ex_5 | AC | 36 ms | 9344 KB |
sep2ex_6 | AC | 37 ms | 9472 KB |
sep2ex_7 | AC | 37 ms | 9472 KB |
sep2ex_8 | AC | 37 ms | 9472 KB |
sep2ex_9 | AC | 37 ms | 9472 KB |
smallrand_0 | AC | 2 ms | 6400 KB |
smallrand_1 | AC | 3 ms | 6400 KB |
smallrand_2 | AC | 3 ms | 6400 KB |
smallrand_3 | AC | 3 ms | 6400 KB |
smallrand_4 | AC | 2 ms | 6400 KB |
smallrand_5 | AC | 2 ms | 6400 KB |
smallrand_6 | AC | 2 ms | 6400 KB |
smallrand_7 | AC | 2 ms | 6400 KB |
smallrand_8 | AC | 3 ms | 6400 KB |
smallrand_9 | AC | 3 ms | 6400 KB |
sparserand_0 | AC | 3 ms | 6528 KB |
sparserand_1 | AC | 3 ms | 6528 KB |
worst2_0 | AC | 39 ms | 11392 KB |
worst2_1 | AC | 103 ms | 11392 KB |
worst2_2 | AC | 39 ms | 11392 KB |
worst2_3 | AC | 117 ms | 11392 KB |
worst_0 | AC | 41 ms | 11392 KB |
worst_1 | AC | 64 ms | 11392 KB |
worst_2 | AC | 39 ms | 11392 KB |
worst_3 | AC | 98 ms | 11392 KB |