Submission #8510033
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define mp make_pair #define PI pair<int,int> #define poly vector<ll> #define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++) #define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--) #define pb push_back #define fi first #define se second inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } #define gc getchar inline ll read(){ ll x = 0; char ch = gc(); bool positive = 1; for (; !isdigit(ch); ch = gc()) if (ch == '-') positive = 0; for (; isdigit(ch); ch = gc()) x = x * 10 + ch - '0'; return positive ? x : -x; } inline void write(ll a){ if(a<0){ a=-a; putchar('-'); } if(a>=10)write(a/10); putchar('0'+a%10); } inline void writeln(ll a){write(a); puts("");} inline void wri(ll a){write(a); putchar(' ');} inline ull rnd(){ return ((ull)rand()<<30^rand())<<4|rand()%4; } const int M=200005,N=1005; int nxt[M],ed[M],ans[M]; vector<int> v[N]; int son[N],vis[N],ne,alb[M],lt[N][N]; void ae(int a,int b){ nxt[++ne]=son[a]; son[a]=ne; ed[ne]=b; } void dfs(int p){ vis[p]=1; for(auto i:v[p])if(!vis[i])dfs(i); } int main(){ int n=read(),m=read(); For(i,1,m){ int s=read(),t=read(); ae(s,t); v[s].pb(t); } For(i,1,n){ memset(vis,0,sizeof(vis)); vector<int> v; vis[i]=1; for(int j=son[i];j;j=nxt[j]){ if(vis[ed[j]]){ alb[j]=1; }else{ dfs(ed[j]); } v.pb(j); } memset(vis,0,sizeof(vis)); vis[i]=1; Rep(o,v.size()-1,0){ int j=v[o]; if(vis[ed[j]]){ alb[j]=1; }else{ dfs(ed[j]); } } For(j,1,n)lt[i][j]=vis[j]; } For(i,1,n)for(int j=son[i];j;j=nxt[j])ans[j]=alb[j]==lt[ed[j]][i]; //for(int i=son[3];i;i=nxt[i])if(ed[i]==4)cout<<alb[i]<<endl; For(i,1,m)puts(ans[i]?"same":"diff"); }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Edges |
User | wzp |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 1960 Byte |
Status | AC |
Exec Time | 407 ms |
Memory | 9856 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 | 399 ms | 9472 KB |
bigcycle_1 | AC | 402 ms | 9472 KB |
dag_0 | AC | 110 ms | 7680 KB |
dag_1 | AC | 189 ms | 9472 KB |
dag_2 | AC | 223 ms | 7680 KB |
dag_3 | AC | 389 ms | 9472 KB |
dag_4 | AC | 171 ms | 8960 KB |
dag_5 | AC | 187 ms | 9472 KB |
dag_6 | AC | 311 ms | 8704 KB |
dag_7 | AC | 390 ms | 9472 KB |
dagex2_0 | AC | 185 ms | 9088 KB |
dagex2_1 | AC | 190 ms | 9472 KB |
dagex2_2 | AC | 180 ms | 9088 KB |
dagex2_3 | AC | 189 ms | 9472 KB |
dagex_0 | AC | 178 ms | 8960 KB |
dagex_1 | AC | 199 ms | 9472 KB |
dagex_2 | AC | 162 ms | 8704 KB |
dagex_3 | AC | 194 ms | 9472 KB |
example_0 | AC | 2 ms | 4352 KB |
example_1 | AC | 2 ms | 2304 KB |
example_2 | AC | 2 ms | 4352 KB |
maxrand_0 | AC | 402 ms | 9472 KB |
maxrand_1 | AC | 388 ms | 9472 KB |
sep2_0 | AC | 394 ms | 9472 KB |
sep2_1 | AC | 407 ms | 9472 KB |
sep2ex_0 | AC | 311 ms | 9728 KB |
sep2ex_1 | AC | 296 ms | 9728 KB |
sep2ex_2 | AC | 272 ms | 9472 KB |
sep2ex_3 | AC | 265 ms | 9472 KB |
sep2ex_4 | AC | 298 ms | 9856 KB |
sep2ex_5 | AC | 285 ms | 9856 KB |
sep2ex_6 | AC | 323 ms | 9472 KB |
sep2ex_7 | AC | 353 ms | 9472 KB |
sep2ex_8 | AC | 374 ms | 9344 KB |
sep2ex_9 | AC | 380 ms | 9344 KB |
smallrand_0 | AC | 2 ms | 4352 KB |
smallrand_1 | AC | 2 ms | 4352 KB |
smallrand_2 | AC | 2 ms | 4352 KB |
smallrand_3 | AC | 2 ms | 2304 KB |
smallrand_4 | AC | 2 ms | 4352 KB |
smallrand_5 | AC | 2 ms | 4480 KB |
smallrand_6 | AC | 2 ms | 2304 KB |
smallrand_7 | AC | 2 ms | 4352 KB |
smallrand_8 | AC | 2 ms | 2304 KB |
smallrand_9 | AC | 2 ms | 4352 KB |
sparserand_0 | AC | 69 ms | 6656 KB |
sparserand_1 | AC | 69 ms | 6656 KB |
worst2_0 | AC | 30 ms | 9600 KB |
worst2_1 | AC | 48 ms | 9728 KB |
worst2_2 | AC | 30 ms | 9344 KB |
worst2_3 | AC | 45 ms | 9344 KB |
worst_0 | AC | 163 ms | 9856 KB |
worst_1 | AC | 188 ms | 9856 KB |
worst_2 | AC | 74 ms | 9344 KB |
worst_3 | AC | 95 ms | 9344 KB |