Submission #3235321
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); // } // } memset(used,0,sizeof(used)); dfs(i,i); } // 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 | birchtree |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1700 Byte |
Status | WA |
Exec Time | 279 ms |
Memory | 8320 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 | WA | 277 ms | 7936 KB |
bigcycle_1 | WA | 275 ms | 7936 KB |
dag_0 | WA | 70 ms | 5888 KB |
dag_1 | WA | 128 ms | 7936 KB |
dag_2 | WA | 142 ms | 5888 KB |
dag_3 | WA | 265 ms | 7936 KB |
dag_4 | WA | 117 ms | 7424 KB |
dag_5 | WA | 127 ms | 7936 KB |
dag_6 | WA | 212 ms | 7168 KB |
dag_7 | WA | 264 ms | 7936 KB |
dagex2_0 | WA | 120 ms | 7552 KB |
dagex2_1 | WA | 129 ms | 7936 KB |
dagex2_2 | WA | 123 ms | 7552 KB |
dagex2_3 | WA | 130 ms | 7936 KB |
dagex_0 | WA | 117 ms | 7424 KB |
dagex_1 | WA | 130 ms | 7936 KB |
dagex_2 | WA | 109 ms | 7168 KB |
dagex_3 | WA | 129 ms | 7936 KB |
example_0 | WA | 2 ms | 2304 KB |
example_1 | AC | 2 ms | 2304 KB |
example_2 | WA | 2 ms | 2304 KB |
maxrand_0 | WA | 274 ms | 7936 KB |
maxrand_1 | WA | 275 ms | 7936 KB |
sep2_0 | WA | 278 ms | 7936 KB |
sep2_1 | WA | 279 ms | 7936 KB |
sep2ex_0 | WA | 201 ms | 8064 KB |
sep2ex_1 | WA | 205 ms | 8064 KB |
sep2ex_2 | WA | 180 ms | 7936 KB |
sep2ex_3 | WA | 181 ms | 7936 KB |
sep2ex_4 | WA | 201 ms | 8192 KB |
sep2ex_5 | WA | 196 ms | 8192 KB |
sep2ex_6 | WA | 221 ms | 7936 KB |
sep2ex_7 | WA | 224 ms | 7936 KB |
sep2ex_8 | WA | 254 ms | 7808 KB |
sep2ex_9 | WA | 255 ms | 7808 KB |
smallrand_0 | WA | 1 ms | 2304 KB |
smallrand_1 | WA | 1 ms | 2304 KB |
smallrand_2 | WA | 1 ms | 2304 KB |
smallrand_3 | AC | 1 ms | 2304 KB |
smallrand_4 | WA | 1 ms | 2304 KB |
smallrand_5 | WA | 2 ms | 2432 KB |
smallrand_6 | AC | 1 ms | 2304 KB |
smallrand_7 | WA | 1 ms | 2304 KB |
smallrand_8 | AC | 1 ms | 2304 KB |
smallrand_9 | WA | 1 ms | 2304 KB |
sparserand_0 | WA | 41 ms | 4608 KB |
sparserand_1 | WA | 41 ms | 4608 KB |
worst2_0 | WA | 26 ms | 8064 KB |
worst2_1 | WA | 38 ms | 8064 KB |
worst2_2 | WA | 26 ms | 7680 KB |
worst2_3 | WA | 35 ms | 7680 KB |
worst_0 | WA | 119 ms | 8320 KB |
worst_1 | WA | 133 ms | 8320 KB |
worst_2 | WA | 55 ms | 7808 KB |
worst_3 | WA | 69 ms | 7808 KB |