Submission #3235321


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);
//			}
//		}
		memset(used,0,sizeof(used));
		dfs(i,i); 
	}
//	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 birchtree
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1700 Byte
Status WA
Exec Time 279 ms
Memory 8320 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 1
WA × 2
AC × 4
WA × 51
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 WA 277 ms 7936 KB
bigcycle_1 WA 275 ms 7936 KB
dag_0 WA 70 ms 5888 KB
dag_1 WA 128 ms 7936 KB
dag_2 WA 142 ms 5888 KB
dag_3 WA 265 ms 7936 KB
dag_4 WA 117 ms 7424 KB
dag_5 WA 127 ms 7936 KB
dag_6 WA 212 ms 7168 KB
dag_7 WA 264 ms 7936 KB
dagex2_0 WA 120 ms 7552 KB
dagex2_1 WA 129 ms 7936 KB
dagex2_2 WA 123 ms 7552 KB
dagex2_3 WA 130 ms 7936 KB
dagex_0 WA 117 ms 7424 KB
dagex_1 WA 130 ms 7936 KB
dagex_2 WA 109 ms 7168 KB
dagex_3 WA 129 ms 7936 KB
example_0 WA 2 ms 2304 KB
example_1 AC 2 ms 2304 KB
example_2 WA 2 ms 2304 KB
maxrand_0 WA 274 ms 7936 KB
maxrand_1 WA 275 ms 7936 KB
sep2_0 WA 278 ms 7936 KB
sep2_1 WA 279 ms 7936 KB
sep2ex_0 WA 201 ms 8064 KB
sep2ex_1 WA 205 ms 8064 KB
sep2ex_2 WA 180 ms 7936 KB
sep2ex_3 WA 181 ms 7936 KB
sep2ex_4 WA 201 ms 8192 KB
sep2ex_5 WA 196 ms 8192 KB
sep2ex_6 WA 221 ms 7936 KB
sep2ex_7 WA 224 ms 7936 KB
sep2ex_8 WA 254 ms 7808 KB
sep2ex_9 WA 255 ms 7808 KB
smallrand_0 WA 1 ms 2304 KB
smallrand_1 WA 1 ms 2304 KB
smallrand_2 WA 1 ms 2304 KB
smallrand_3 AC 1 ms 2304 KB
smallrand_4 WA 1 ms 2304 KB
smallrand_5 WA 2 ms 2432 KB
smallrand_6 AC 1 ms 2304 KB
smallrand_7 WA 1 ms 2304 KB
smallrand_8 AC 1 ms 2304 KB
smallrand_9 WA 1 ms 2304 KB
sparserand_0 WA 41 ms 4608 KB
sparserand_1 WA 41 ms 4608 KB
worst2_0 WA 26 ms 8064 KB
worst2_1 WA 38 ms 8064 KB
worst2_2 WA 26 ms 7680 KB
worst2_3 WA 35 ms 7680 KB
worst_0 WA 119 ms 8320 KB
worst_1 WA 133 ms 8320 KB
worst_2 WA 55 ms 7808 KB
worst_3 WA 69 ms 7808 KB