Submission #3234167

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
void File(){
    freopen("ARC92F.in","r",stdin);
    freopen("ARC92F.out","w",stdout);
}
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
#define mem(a) memset(a,0,sizeof(a))
const int maxn=1000+10;
const int maxm=200000+10;
vector<int>E[maxn];
int n,m,beg[maxn],len,num[maxn][maxn];
bool can[maxn][maxn],vis[maxn],can1[maxn][maxn];
int vis1[maxn],vis2[maxn],from[maxm],to[maxm];
void dfs(int u,int rt){
    vis[u]=1;
    can[rt][u]=1;
    int size=E[u].size()-1;
    REP(i,0,size){
        int v=E[u][i];
        if(vis[v])continue;
        dfs(v,rt);
    }
}
void dfs1(int u){
    vis[u]=1;
    int size=E[u].size()-1;
    REP(i,0,size){
        int v=E[u][i];
        if(vis[v])continue;
        vis1[v]=num[u][v];
        dfs1(v);
    }
}
void dfs2(int u){
    vis[u]=1;
    int size=E[u].size()-1;
    DREP(i,size,0){
        int v=E[u][i];
        if(vis[v])continue;
        vis2[v]=num[u][v];
        dfs2(v);
    }
}
int main(){
    //File();
    scanf("%d%d",&n,&m);
    REP(i,1,m){
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        num[u][v]=++len;
        from[len]=u;
        to[len]=v;
    }
    REP(i,1,n){
        dfs(i,i);
        mem(vis);
    }
    REP(i,1,n){
        dfs1(i);
        mem(vis);
        dfs2(i);
        mem(vis);
        int size=E[i].size()-1;
        REP(j,0,size){
            int v=E[i][j];
            if(vis1[v]!=num[i][v] || vis2[v]!=num[i][v])
                can1[i][v]=1;
        }
        mem(vis1);
        mem(vis2);
    }
    REP(i,1,m){
        int u=from[i],v=to[i];
        if((can[v][u]^can1[u][v])==0)
            puts("same");
        else puts("diff");
    }
    return 0;
}//

Submission Info

Judge Result