Submission #10250732

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <vector>

const int MN = 1005, MM = 200005;

int N, M, eu[MM], ev[MM], Ans[MM];
std::vector<int> G[MN];
bool vis[MN], rch[MN][MN]; int col[MN];
void DFS(int u, int c) {
	vis[u] = 1, col[u] ^= c;
	for (auto i : G[u]) if (!vis[ev[i]]) DFS(ev[i], c);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		scanf("%d%d", &eu[i], &ev[i]);
		G[eu[i]].push_back(i);
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) vis[j] = 0;
		DFS(i, 0);
		for (int j = 1; j <= N; ++j) if (vis[j]) rch[i][j] = 1;
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) col[j] = vis[j] = 0; vis[i] = 1;
		for (auto j : G[i]) if (!vis[ev[j]]) DFS(ev[j], ev[j]);
		std::reverse(G[i].begin(), G[i].end());
		for (int j = 1; j <= N; ++j) vis[j] = 0; vis[i] = 1;
		for (auto j : G[i]) if (!vis[ev[j]]) DFS(ev[j], ev[j]);
		for (auto j : G[i]) Ans[j] = rch[ev[j]][i] ^ !!col[ev[j]];
	}
	for (int i = 1; i <= M; ++i) puts(Ans[i] ? "diff" : "same");
	return 0;
}

Submission Info

Submission Time
Task F - Two Faced Edges
User PinkRabbit
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 1060 Byte
Status AC
Exec Time 1380 ms
Memory 6144 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:16:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:18:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &eu[i], &ev[i]);
                                ^

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 1343 ms 5632 KiB
bigcycle_1 AC 1337 ms 5760 KiB
dag_0 AC 275 ms 3328 KiB
dag_1 AC 594 ms 5760 KiB
dag_2 AC 585 ms 3328 KiB
dag_3 AC 1319 ms 5760 KiB
dag_4 AC 526 ms 5120 KiB
dag_5 AC 591 ms 5760 KiB
dag_6 AC 988 ms 4864 KiB
dag_7 AC 1310 ms 5760 KiB
dagex2_0 AC 542 ms 5248 KiB
dagex2_1 AC 596 ms 5760 KiB
dagex2_2 AC 554 ms 5248 KiB
dagex2_3 AC 599 ms 5760 KiB
dagex_0 AC 515 ms 5120 KiB
dagex_1 AC 598 ms 5760 KiB
dagex_2 AC 476 ms 4864 KiB
dagex_3 AC 598 ms 5760 KiB
example_0 AC 1 ms 256 KiB
example_1 AC 1 ms 256 KiB
example_2 AC 1 ms 256 KiB
maxrand_0 AC 1323 ms 5632 KiB
maxrand_1 AC 1324 ms 5632 KiB
sep2_0 AC 1380 ms 5760 KiB
sep2_1 AC 1359 ms 5760 KiB
sep2ex_0 AC 926 ms 5888 KiB
sep2ex_1 AC 957 ms 5888 KiB
sep2ex_2 AC 823 ms 5632 KiB
sep2ex_3 AC 821 ms 5632 KiB
sep2ex_4 AC 934 ms 6016 KiB
sep2ex_5 AC 930 ms 6016 KiB
sep2ex_6 AC 1062 ms 5632 KiB
sep2ex_7 AC 1073 ms 5760 KiB
sep2ex_8 AC 1215 ms 5632 KiB
sep2ex_9 AC 1227 ms 5632 KiB
smallrand_0 AC 1 ms 256 KiB
smallrand_1 AC 1 ms 256 KiB
smallrand_2 AC 1 ms 256 KiB
smallrand_3 AC 1 ms 256 KiB
smallrand_4 AC 1 ms 256 KiB
smallrand_5 AC 1 ms 256 KiB
smallrand_6 AC 1 ms 256 KiB
smallrand_7 AC 1 ms 256 KiB
smallrand_8 AC 1 ms 256 KiB
smallrand_9 AC 2 ms 256 KiB
sparserand_0 AC 120 ms 1536 KiB
sparserand_1 AC 121 ms 1536 KiB
worst2_0 AC 47 ms 5888 KiB
worst2_1 AC 105 ms 5888 KiB
worst2_2 AC 47 ms 5504 KiB
worst2_3 AC 93 ms 5504 KiB
worst_0 AC 531 ms 6144 KiB
worst_1 AC 605 ms 6144 KiB
worst_2 AC 202 ms 5632 KiB
worst_3 AC 273 ms 5632 KiB