Submission #8502026
Source Code Expand
// #pragma GCC target("avx2") // CPU 処理並列化 // #pragma GCC optimize("O3") // CPU 処理並列化 // #pragma GCC optimize("unroll-loops") // 条件処理の呼び出しを減らす #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<deque> #include<stack> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<bitset> #include<stdlib.h> #include<cassert> #include<time.h> #include<bitset> #include<numeric> #include<unordered_set> #include<complex> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; const long long d2=(mod+1)/2; const double EPS=1e-10; const double INF=1e+10; const double PI=acos(-1.0); const int C_SIZE = 5121000; namespace{ long long fact[C_SIZE]; long long finv[C_SIZE]; long long inv[C_SIZE]; long long Comb(int a,int b){ if(a<b||b<0)return 0; return fact[a]*finv[b]%mod*finv[a-b]%mod; } void init_C(int n){ fact[0]=finv[0]=inv[1]=1; for(int i=2;i<n;i++){ inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod; } for(int i=1;i<n;i++){ fact[i]=fact[i-1]*i%mod; finv[i]=finv[i-1]*inv[i]%mod; } } long long pw(long long a,long long b){ if(a<0LL)return 0; if(b<0LL)return 0; long long ret=1; while(b){ if(b%2)ret=ret*a%mod; a=a*a%mod; b/=2; } return ret; } long long pw_mod(long long a,long long b,long long M){ if(a<0LL)return 0; if(b<0LL)return 0; long long ret=1; while(b){ if(b%2)ret=ret*a%M; a=a*a%M; b/=2; } return ret; } int pw_mod_int(int a,int b,int M){ if(a<0)return 0; if(b<0)return 0; int ret=1; while(b){ if(b%2)ret=(long long)ret*a%M; a=(long long)a*a%M; b/=2; } return ret; } int ABS(int a){return max(a,-a);} long long ABS(long long a){return max(a,-a);} double ABS(double a){return max(a,-a);} int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; } } // ここから編集しろ int x[210000]; int y[210000]; int ans[210000]; int v[2100]; vector<pair<int,int> >g[2100]; int L[2100]; int R[2100]; void dfs1(int a,int b){ L[a]=b; for(int i=0;i<g[a].size();i++){ if(~L[g[a][i].first])continue; dfs1(g[a][i].first,b); } } void dfs2(int a,int b){ R[a]=b; for(int i=0;i<g[a].size();i++){ if(~R[g[a][i].first])continue; dfs2(g[a][i].first,b); } } int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ int p,q;scanf("%d%d",&p,&q); p--;q--; x[i]=p; y[i]=q; g[p].push_back(make_pair(q,i)); } for(int i=0;i<a;i++){ for(int j=0;j<a;j++)v[j]=0; v[i]=1; queue<int>Q; Q.push(i); while(Q.size()){ int at=Q.front(); Q.pop(); for(int j=0;j<g[at].size();j++){ int to=g[at][j].first; if(v[to])continue; v[to]=1; Q.push(to); } } for(int j=0;j<g[i].size();j++){ if(v[g[i][j].first])ans[g[i][j].second]++; } } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ L[j]=R[j]=-1; } L[i]=R[i]=0; for(int j=0;j<g[i].size();j++){ if(L[g[i][j].first]==-1)dfs1(g[i][j].first,j); } for(int j=g[i].size();j>0;j--){ if(R[g[i][j-1].first]==-1)dfs2(g[i][j-1].first,j-1); } for(int j=0;j<g[i].size();j++){ if(L[g[i][j].first]!=j||R[g[i][j].first]!=j)ans[g[i][j].second]++; } } for(int i=0;i<b;i++){ // printf("%d ",ans[i]); if(ans[i]==1)printf("diff\n"); else printf("same\n"); } }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Edges |
User | tozangezan |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3464 Byte |
Status | WA |
Exec Time | 859 ms |
Memory | 6656 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:111:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int a,b;scanf("%d%d",&a,&b); ^ ./Main.cpp:113:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int p,q;scanf("%d%d",&p,&q); ^
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 | 859 ms | 5888 KB |
bigcycle_1 | WA | 853 ms | 5888 KB |
dag_0 | WA | 208 ms | 2816 KB |
dag_1 | WA | 378 ms | 6016 KB |
dag_2 | WA | 440 ms | 2944 KB |
dag_3 | WA | 825 ms | 6016 KB |
dag_4 | WA | 342 ms | 5248 KB |
dag_5 | WA | 377 ms | 6016 KB |
dag_6 | WA | 653 ms | 4864 KB |
dag_7 | WA | 822 ms | 6016 KB |
dagex2_0 | WA | 350 ms | 5248 KB |
dagex2_1 | WA | 379 ms | 6016 KB |
dagex2_2 | WA | 357 ms | 5376 KB |
dagex2_3 | WA | 379 ms | 6016 KB |
dagex_0 | WA | 336 ms | 5120 KB |
dagex_1 | WA | 380 ms | 6016 KB |
dagex_2 | WA | 317 ms | 4864 KB |
dagex_3 | WA | 381 ms | 6016 KB |
example_0 | WA | 1 ms | 256 KB |
example_1 | AC | 1 ms | 256 KB |
example_2 | AC | 1 ms | 256 KB |
maxrand_0 | AC | 838 ms | 5760 KB |
maxrand_1 | AC | 837 ms | 5760 KB |
sep2_0 | AC | 846 ms | 5888 KB |
sep2_1 | AC | 851 ms | 5888 KB |
sep2ex_0 | WA | 604 ms | 6272 KB |
sep2ex_1 | WA | 616 ms | 6272 KB |
sep2ex_2 | WA | 534 ms | 5888 KB |
sep2ex_3 | WA | 532 ms | 5888 KB |
sep2ex_4 | WA | 602 ms | 6528 KB |
sep2ex_5 | WA | 602 ms | 6528 KB |
sep2ex_6 | WA | 670 ms | 5888 KB |
sep2ex_7 | WA | 684 ms | 5888 KB |
sep2ex_8 | WA | 775 ms | 5760 KB |
sep2ex_9 | WA | 779 ms | 5760 KB |
smallrand_0 | AC | 1 ms | 256 KB |
smallrand_1 | AC | 1 ms | 256 KB |
smallrand_2 | WA | 1 ms | 256 KB |
smallrand_3 | WA | 1 ms | 256 KB |
smallrand_4 | AC | 1 ms | 256 KB |
smallrand_5 | AC | 1 ms | 256 KB |
smallrand_6 | WA | 1 ms | 256 KB |
smallrand_7 | AC | 1 ms | 256 KB |
smallrand_8 | WA | 1 ms | 256 KB |
smallrand_9 | AC | 1 ms | 256 KB |
sparserand_0 | AC | 124 ms | 640 KB |
sparserand_1 | AC | 122 ms | 640 KB |
worst2_0 | WA | 42 ms | 6272 KB |
worst2_1 | WA | 78 ms | 6400 KB |
worst2_2 | WA | 41 ms | 5632 KB |
worst2_3 | WA | 70 ms | 5632 KB |
worst_0 | WA | 335 ms | 6656 KB |
worst_1 | WA | 383 ms | 6656 KB |
worst_2 | WA | 133 ms | 5760 KB |
worst_3 | WA | 177 ms | 5760 KB |