Submission #19892290

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e3+11;
const int MAXM=2e5+11;
int N,M,U[MAXM],V[MAXM],vis[MAXN][MAXN],G[MAXN][MAXN]; vector<int> vec[MAXN];
void dfs(int u,int st){
    vis[st][u]=1; for(auto v:vec[u]) if(!vis[st][v]) dfs(v,st);
    return;
}
int col1[MAXN],col2[MAXN];
void dfs1(int u,int p){
    col1[u]=p; for(auto v:vec[u]) if(!col1[v]) dfs1(v,p);
    return;
}
void dfs2(int u,int p){
    col2[u]=p; for(auto v:vec[u]) if(!col2[v]) dfs2(v,p);
}
int main(){
    N=read(),M=read(); for(int i=1;i<=M;i++){U[i]=read(),V[i]=read();vec[U[i]].pb(V[i]);}
    for(int i=1;i<=N;i++) dfs(i,i);
    for(int i=1;i<=N;i++){
        memset(col1,0,sizeof(col1)),memset(col2,0,sizeof(col2));
        col1[i]=col2[i]=1;
        for(auto v:vec[i]) if(!col1[v]) dfs1(v,v);
        for(int j=vec[i].size()-1;j>=0;j--){int v=vec[i][j]; if(!col2[v]) dfs2(v,v);}
        for(auto v:vec[i])
            G[i][v]=(col1[v]==col2[v]);
    }
    for(int i=1;i<=M;i++){
        int u=U[i],v=V[i]; bool f=(vis[v][u]^G[u][v]);
        if(f) printf("same\n"); else printf("diff\n");
    }return 0;
}
/*
5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5
*/

Submission Info

Submission Time
Task F - Two Faced Edges
User Limpid_
Language C++ (GCC 9.2.1)
Score 1100
Code Size 1553 Byte
Status AC
Exec Time 615 ms
Memory 14428 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 3
AC × 55
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 603 ms 14088 KiB
bigcycle_1 AC 594 ms 14076 KiB
dag_0 AC 149 ms 12604 KiB
dag_1 AC 264 ms 14272 KiB
dag_2 AC 296 ms 12812 KiB
dag_3 AC 565 ms 14260 KiB
dag_4 AC 237 ms 13904 KiB
dag_5 AC 264 ms 14276 KiB
dag_6 AC 441 ms 13680 KiB
dag_7 AC 577 ms 14088 KiB
dagex2_0 AC 242 ms 13904 KiB
dagex2_1 AC 261 ms 14136 KiB
dagex2_2 AC 251 ms 13968 KiB
dagex2_3 AC 260 ms 14108 KiB
dagex_0 AC 235 ms 13864 KiB
dagex_1 AC 259 ms 14240 KiB
dagex_2 AC 221 ms 13588 KiB
dagex_3 AC 263 ms 14100 KiB
example_0 AC 5 ms 3460 KiB
example_1 AC 2 ms 3452 KiB
example_2 AC 2 ms 3616 KiB
maxrand_0 AC 591 ms 14156 KiB
maxrand_1 AC 583 ms 14040 KiB
sep2_0 AC 611 ms 14084 KiB
sep2_1 AC 615 ms 14280 KiB
sep2ex_0 AC 411 ms 14320 KiB
sep2ex_1 AC 416 ms 14360 KiB
sep2ex_2 AC 365 ms 14160 KiB
sep2ex_3 AC 368 ms 13984 KiB
sep2ex_4 AC 420 ms 14428 KiB
sep2ex_5 AC 414 ms 14428 KiB
sep2ex_6 AC 469 ms 14000 KiB
sep2ex_7 AC 474 ms 14160 KiB
sep2ex_8 AC 545 ms 13900 KiB
sep2ex_9 AC 549 ms 13992 KiB
smallrand_0 AC 8 ms 3540 KiB
smallrand_1 AC 2 ms 3776 KiB
smallrand_2 AC 2 ms 3404 KiB
smallrand_3 AC 2 ms 3444 KiB
smallrand_4 AC 2 ms 3664 KiB
smallrand_5 AC 3 ms 3592 KiB
smallrand_6 AC 2 ms 3660 KiB
smallrand_7 AC 1 ms 3672 KiB
smallrand_8 AC 2 ms 3592 KiB
smallrand_9 AC 3 ms 3652 KiB
sparserand_0 AC 111 ms 11572 KiB
sparserand_1 AC 110 ms 11488 KiB
worst2_0 AC 37 ms 12484 KiB
worst2_1 AC 64 ms 12572 KiB
worst2_2 AC 33 ms 12600 KiB
worst2_3 AC 58 ms 12692 KiB
worst_0 AC 239 ms 14264 KiB
worst_1 AC 277 ms 13768 KiB
worst_2 AC 101 ms 12900 KiB
worst_3 AC 135 ms 13576 KiB