Submission #26261701

Source Code Expand

#include<bits/stdc++.h>
#define N (1010)
#define M (200010)
using namespace std;
int n,m,u[M],v[M],used[N],tag[N],f[N][N];
vector<int>e[N];
inline int read(){
	int w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
inline void dfs(int st,int rt){
	if(!used[st]) used[st]=1,tag[st]=rt;
	else{
		if(rt!=tag[st]) ++used[st];
		else return;
		if(used[st]>2) return;
	}
	for(int i=0;i<(int)e[st].size();i++){
		int ed=e[st][i];
		if(used[ed]<2) dfs(ed,rt);
	}
	return;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		u[i]=read(),v[i]=read();
		e[u[i]].push_back(v[i]);
	}
	for(int i=1;i<=n;i++){
		memset(used,0,sizeof(used));
		used[i]=n;
		for(int j=0;j<(int)e[i].size();j++) dfs(e[i][j],e[i][j]);
		for(int j=1;j<=n;j++) f[i][j]=used[j];
	}
	for(int i=1;i<=m;i++){
		if(f[v[i]][u[i]]&&(f[u[i]][v[i]]>1)) puts("same");
		else if((!f[v[i]][u[i]])&&(f[u[i]][v[i]]==1)) puts("same");
		else puts("diff");
	}
	return 0;
}

Submission Info

Submission Time
Task F - Two Faced Edges
User xxbbkk
Language C++ (GCC 9.2.1)
Score 1100
Code Size 1071 Byte
Status AC
Exec Time 1019 ms
Memory 10692 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 904 ms 10340 KiB
bigcycle_1 AC 898 ms 10284 KiB
dag_0 AC 197 ms 8692 KiB
dag_1 AC 367 ms 10376 KiB
dag_2 AC 427 ms 8912 KiB
dag_3 AC 873 ms 10396 KiB
dag_4 AC 327 ms 9964 KiB
dag_5 AC 361 ms 10248 KiB
dag_6 AC 678 ms 9688 KiB
dag_7 AC 861 ms 10376 KiB
dagex2_0 AC 344 ms 10036 KiB
dagex2_1 AC 372 ms 10220 KiB
dagex2_2 AC 366 ms 10056 KiB
dagex2_3 AC 387 ms 10404 KiB
dagex_0 AC 327 ms 9900 KiB
dagex_1 AC 375 ms 10216 KiB
dagex_2 AC 326 ms 9856 KiB
dagex_3 AC 392 ms 10344 KiB
example_0 AC 4 ms 3624 KiB
example_1 AC 2 ms 3556 KiB
example_2 AC 2 ms 3624 KiB
maxrand_0 AC 883 ms 10220 KiB
maxrand_1 AC 882 ms 10308 KiB
sep2_0 AC 890 ms 10264 KiB
sep2_1 AC 898 ms 10280 KiB
sep2ex_0 AC 593 ms 10316 KiB
sep2ex_1 AC 604 ms 10476 KiB
sep2ex_2 AC 602 ms 10132 KiB
sep2ex_3 AC 606 ms 10252 KiB
sep2ex_4 AC 743 ms 10640 KiB
sep2ex_5 AC 728 ms 10684 KiB
sep2ex_6 AC 892 ms 10292 KiB
sep2ex_7 AC 908 ms 10292 KiB
sep2ex_8 AC 1000 ms 10192 KiB
sep2ex_9 AC 1019 ms 10260 KiB
smallrand_0 AC 5 ms 3596 KiB
smallrand_1 AC 2 ms 3736 KiB
smallrand_2 AC 3 ms 3624 KiB
smallrand_3 AC 2 ms 3612 KiB
smallrand_4 AC 2 ms 3720 KiB
smallrand_5 AC 2 ms 3672 KiB
smallrand_6 AC 2 ms 3500 KiB
smallrand_7 AC 2 ms 3592 KiB
smallrand_8 AC 2 ms 3592 KiB
smallrand_9 AC 2 ms 3720 KiB
sparserand_0 AC 121 ms 7780 KiB
sparserand_1 AC 114 ms 7640 KiB
worst2_0 AC 33 ms 10460 KiB
worst2_1 AC 70 ms 10348 KiB
worst2_2 AC 31 ms 10156 KiB
worst2_3 AC 64 ms 10188 KiB
worst_0 AC 325 ms 10692 KiB
worst_1 AC 399 ms 10168 KiB
worst_2 AC 118 ms 9728 KiB
worst_3 AC 183 ms 10096 KiB