Submission #3233766
Source Code Expand
#include<iostream> #include<cstdio> #include<cstring> #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; struct edge{ int from; int to; int next; }E[maxm]; int sz=0; int head[maxn]; void add_edge(int u,int v){ sz++; E[sz].from=u; E[sz].to=v; E[sz].next=head[u]; head[u]=sz; } int used[maxn]; int route[maxn][maxn]; void dfs(int s,int x){ int y; used[x]=1; route[s][x]++; for(int i=head[x];i;i=E[i].next){ y=E[i].to; 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); u=qread(); v=qread(); add_edge(u,v); } int y; for(int i=1;i<=n;i++){ for(int j=head[i];j;j=E[j].next){ y=E[j].to; 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(E[i].from,E[i].to)) qprint(b,4); else qprint(a,4); } }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Edges |
User | vjudge5 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1590 Byte |
Status | TLE |
Exec Time | 5255 ms |
Memory | 7552 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 | TLE | 5255 ms | 6528 KB |
bigcycle_1 | TLE | 5255 ms | 6528 KB |
dag_0 | AC | 1089 ms | 6784 KB |
dag_1 | AC | 2474 ms | 7552 KB |
dag_2 | AC | 2503 ms | 6784 KB |
dag_3 | TLE | 5255 ms | 6528 KB |
dag_4 | AC | 2195 ms | 7296 KB |
dag_5 | AC | 2465 ms | 7552 KB |
dag_6 | AC | 4364 ms | 7168 KB |
dag_7 | TLE | 5255 ms | 6528 KB |
dagex2_0 | AC | 2265 ms | 7296 KB |
dagex2_1 | AC | 2493 ms | 7552 KB |
dagex2_2 | AC | 2324 ms | 7296 KB |
dagex2_3 | AC | 2507 ms | 7552 KB |
dagex_0 | AC | 2149 ms | 7168 KB |
dagex_1 | AC | 2498 ms | 7552 KB |
dagex_2 | AC | 1994 ms | 7168 KB |
dagex_3 | AC | 2519 ms | 7552 KB |
example_0 | AC | 2 ms | 2304 KB |
example_1 | AC | 2 ms | 2304 KB |
example_2 | AC | 2 ms | 2304 KB |
maxrand_0 | TLE | 5255 ms | 6528 KB |
maxrand_1 | TLE | 5255 ms | 6528 KB |
sep2_0 | TLE | 5255 ms | 6528 KB |
sep2_1 | TLE | 5255 ms | 6528 KB |
sep2ex_0 | AC | 3819 ms | 7552 KB |
sep2ex_1 | AC | 3891 ms | 7552 KB |
sep2ex_2 | AC | 3423 ms | 7552 KB |
sep2ex_3 | AC | 3426 ms | 7552 KB |
sep2ex_4 | AC | 4011 ms | 7552 KB |
sep2ex_5 | AC | 3954 ms | 7552 KB |
sep2ex_6 | AC | 4647 ms | 7552 KB |
sep2ex_7 | AC | 4725 ms | 7552 KB |
sep2ex_8 | TLE | 5255 ms | 6528 KB |
sep2ex_9 | TLE | 5255 ms | 6528 KB |
smallrand_0 | AC | 1 ms | 2304 KB |
smallrand_1 | AC | 1 ms | 2304 KB |
smallrand_2 | AC | 1 ms | 2304 KB |
smallrand_3 | AC | 1 ms | 2304 KB |
smallrand_4 | AC | 1 ms | 2304 KB |
smallrand_5 | AC | 1 ms | 2304 KB |
smallrand_6 | AC | 1 ms | 2304 KB |
smallrand_7 | AC | 1 ms | 2304 KB |
smallrand_8 | AC | 1 ms | 2304 KB |
smallrand_9 | AC | 1 ms | 2304 KB |
sparserand_0 | AC | 140 ms | 4352 KB |
sparserand_1 | AC | 140 ms | 4352 KB |
worst2_0 | AC | 45 ms | 6528 KB |
worst2_1 | AC | 263 ms | 6784 KB |
worst2_2 | AC | 46 ms | 6784 KB |
worst2_3 | AC | 207 ms | 6912 KB |
worst_0 | AC | 1807 ms | 7296 KB |
worst_1 | AC | 2526 ms | 7424 KB |
worst_2 | AC | 508 ms | 7168 KB |
worst_3 | AC | 992 ms | 7296 KB |