Submission #3235324


Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define maxn 1005
#define maxm 200005
using namespace std;
inline int qread(){
	int x=0,sign=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') sign=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*sign;
}
int n,m; 
int s[maxm],e[maxm];
vector<int>E[maxn];
void add_edge(int u,int v){
	E[u].push_back(v);
}
int used[maxn];
int route[maxn][maxn];
void dfs(int s,int x){
	int y;
	used[x]=1;
	route[s][x]++;
	int cnt=E[x].size();
	for(int i=0;i<cnt;i++){
		y=E[x][i];
		if(y==s) continue;
		if(!used[y]&&route[s][y]<2){
			dfs(s,y);
		}
	}
}

int judge(int u,int v){//1为diff,0为same 
	if(route[v][u]>0){//在一个SCC中 
		if(route[u][v]>=2) return 0;
		else return 1; 
	}else{//不在一个SCC中 
		if(route[u][v]>=2) return 1;
		else return 0;
	}
}

char a[]="same",b[]="diff";
void qprint(char *s,int len){
	for(int i=0;i<len;i++){
		putchar(s[i]);
	}
	putchar('\n');
}
int main(){
//	scanf("%d %d",&n,&m);
	n=qread();
	m=qread(); 
	int u,v;
	for(int i=1;i<=m;i++){
//		scanf("%d %d",&u,&v);
		s[i]=qread();
		e[i]=qread();
		add_edge(s[i],e[i]);
	}
	int y;
	for(int i=1;i<=n;i++){
		int cnt=E[i].size();
		for(int j=0;j<cnt;j++){
			y=E[i][j];
			if(route[i][y]<2){
				memset(used,0,sizeof(used));
				dfs(i,y);
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			printf("%d ",route[i][j]);
//		}
//		printf("\n");
//	}
	for(int i=1;i<=m;i++){
		if(judge(s[i],e[i]) )qprint(b,4);
		else qprint(a,4);
	}
}

Submission Info

Submission Time
Task F - Two Faced Edges
User vjudge4
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 1547 Byte
Status AC
Exec Time 997 ms
Memory 8192 KB

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 534 ms 7936 KB
bigcycle_1 AC 528 ms 7936 KB
dag_0 AC 233 ms 5888 KB
dag_1 AC 461 ms 7936 KB
dag_2 AC 277 ms 5888 KB
dag_3 AC 507 ms 7936 KB
dag_4 AC 415 ms 7424 KB
dag_5 AC 461 ms 7936 KB
dag_6 AC 407 ms 7168 KB
dag_7 AC 506 ms 7936 KB
dagex2_0 AC 434 ms 7552 KB
dagex2_1 AC 474 ms 7936 KB
dagex2_2 AC 455 ms 7552 KB
dagex2_3 AC 477 ms 7936 KB
dagex_0 AC 405 ms 7424 KB
dagex_1 AC 481 ms 7936 KB
dagex_2 AC 397 ms 7168 KB
dagex_3 AC 486 ms 7936 KB
example_0 AC 1 ms 2304 KB
example_1 AC 1 ms 2304 KB
example_2 AC 2 ms 2304 KB
maxrand_0 AC 523 ms 7936 KB
maxrand_1 AC 522 ms 7936 KB
sep2_0 AC 527 ms 7936 KB
sep2_1 AC 529 ms 7936 KB
sep2ex_0 AC 402 ms 8064 KB
sep2ex_1 AC 402 ms 8064 KB
sep2ex_2 AC 529 ms 7936 KB
sep2ex_3 AC 537 ms 7936 KB
sep2ex_4 AC 738 ms 8192 KB
sep2ex_5 AC 714 ms 8192 KB
sep2ex_6 AC 930 ms 7936 KB
sep2ex_7 AC 956 ms 7936 KB
sep2ex_8 AC 992 ms 7808 KB
sep2ex_9 AC 997 ms 7808 KB
smallrand_0 AC 1 ms 2304 KB
smallrand_1 AC 1 ms 2304 KB
smallrand_2 AC 1 ms 2304 KB
smallrand_3 AC 1 ms 2304 KB
smallrand_4 AC 1 ms 2304 KB
smallrand_5 AC 1 ms 2432 KB
smallrand_6 AC 1 ms 2304 KB
smallrand_7 AC 2 ms 2304 KB
smallrand_8 AC 2 ms 2304 KB
smallrand_9 AC 2 ms 2304 KB
sparserand_0 AC 85 ms 4608 KB
sparserand_1 AC 82 ms 4608 KB
worst2_0 AC 45 ms 7168 KB
worst2_1 AC 56 ms 7296 KB
worst2_2 AC 45 ms 6912 KB
worst2_3 AC 54 ms 7168 KB
worst_0 AC 181 ms 8064 KB
worst_1 AC 239 ms 8192 KB
worst_2 AC 81 ms 7424 KB
worst_3 AC 120 ms 7424 KB