oj.uz

Submission #126674

# Submission time Handle Problem Language Result Execution time Memory
126674 2019-07-08T09:08:27 Z abacaba Ronald (COCI17_ronald) C++14
120 / 120
 60 ms 1372 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 15;
int n, m, p[N], sz[N];
bool g[N][N], used[N], was[N];

int find(int v) {
	if(v == p[v])
		return v;
	return p[v] = find(p[v]);
}

void unio(int a, int b) {
	a = find(a);
	b = find(b);
	if(a != b) {
		if(sz[a] < sz[b])
			swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
}

bool dfs(int v, bool rev) {
	used[v] = true;
	if(rev)
		for(int i = 1; i <= n; ++i) {
			g[i][v] ^= 1;
			g[v][i] ^= 1;
		}
	for(int i = 1; i <= n; ++i)
		if(i != v && !g[i][v])
			if(used[i] || !dfs(i, 1))
				return false;
	return true;
}
 
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		p[i] = i, sz[i] = 1;
	for(int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		unio(u, v);
		g[u][v] = g[v][u] = true;
	}
	for(int i = 1; i <= n; ++i) {
		if(!was[find(i)]) {
			memset(used, 0, sizeof(used));
			bool flag1 = dfs(i, 0);

			memset(used, 0, sizeof(used));
			bool flag2 = dfs(i, 1);
			if(!flag1 && !flag2) {
				puts("NE");
				return 0;
			}
			was[find(i)] = true;
		}
	}
	puts("DA");
    return 0;
}

Compilation message

ronald.cpp: In function 'int main()':
ronald.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
ronald.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 508 KB Output is correct
2 Correct 15 ms 928 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 5 ms 632 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 10 ms 760 KB Output is correct
3 Correct 34 ms 1372 KB Output is correct
4 Correct 60 ms 1372 KB Output is correct