Submission #8509955

---

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

Judge Result