oj.uz

Submission #38905

# Submission time Handle Problem Language Result Execution time Memory
38905 2018-01-07T18:41:13 Z adamczh1 Game (IOI14_game) C++14
15 / 100
 0 ms 10808 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
	vector<int> data;
	vector<int> remaining;
	void init(int n) { data.assign(n, -1); remaining.assign(n, n-1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
			remaining[x] += remaining[y];
			remaining[x] -= 2;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
} uf;
int cnt;
bool saidyes=0;
bool danger=0;
int N;
void initialize(int n) {
	uf.init(n);
	N=n;
	cnt=n*(n-1)/2;
}

int hasEdge(int u, int v) {
	if(cnt==N-1 && !saidyes){
		danger=1;
	}
	if(danger){
		return 1;
	}
	cnt--;
	if(!uf.findSet(u,v) && (uf.remaining[uf.root(u)]==1 || uf.remaining[uf.root(v)]==1)){
		uf.unionSet(u,v);
		saidyes=1;
		return 1;
	}
	if(!uf.findSet(u,v)){
		uf.remaining[uf.root(u)]--;
		uf.remaining[uf.root(v)]--;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10808 KB Output is correct
2 Correct 0 ms 10808 KB Output is correct
3 Correct 0 ms 10808 KB Output is correct
4 Correct 0 ms 10808 KB Output is correct
5 Correct 0 ms 10808 KB Output is correct
6 Correct 0 ms 10808 KB Output is correct
7 Correct 0 ms 10808 KB Output is correct
8 Correct 0 ms 10808 KB Output is correct
9 Correct 0 ms 10808 KB Output is correct
10 Correct 0 ms 10808 KB Output is correct
11 Correct 0 ms 10808 KB Output is correct
12 Correct 0 ms 10808 KB Output is correct
13 Correct 0 ms 10808 KB Output is correct
14 Correct 0 ms 10808 KB Output is correct
15 Correct 0 ms 10808 KB Output is correct
16 Correct 0 ms 10808 KB Output is correct
17 Correct 0 ms 10808 KB Output is correct
18 Correct 0 ms 10808 KB Output is correct
19 Correct 0 ms 10808 KB Output is correct
20 Correct 0 ms 10808 KB Output is correct
21 Correct 0 ms 10808 KB Output is correct
22 Correct 0 ms 10808 KB Output is correct
23 Correct 0 ms 10808 KB Output is correct
24 Correct 0 ms 10808 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10808 KB Output is correct
2 Correct 0 ms 10808 KB Output is correct
3 Correct 0 ms 10808 KB Output is correct
4 Correct 0 ms 10808 KB Output is correct
5 Correct 0 ms 10808 KB Output is correct
6 Correct 0 ms 10808 KB Output is correct
7 Correct 0 ms 10808 KB Output is correct
8 Correct 0 ms 10808 KB Output is correct
9 Correct 0 ms 10808 KB Output is correct
10 Correct 0 ms 10808 KB Output is correct
11 Correct 0 ms 10808 KB Output is correct
12 Correct 0 ms 10808 KB Output is correct
13 Correct 0 ms 10808 KB Output is correct
14 Correct 0 ms 10808 KB Output is correct
15 Correct 0 ms 10808 KB Output is correct
16 Correct 0 ms 10808 KB Output is correct
17 Correct 0 ms 10808 KB Output is correct
18 Correct 0 ms 10808 KB Output is correct
19 Correct 0 ms 10808 KB Output is correct
20 Correct 0 ms 10808 KB Output is correct
21 Correct 0 ms 10808 KB Output is correct
22 Correct 0 ms 10808 KB Output is correct
23 Correct 0 ms 10808 KB Output is correct
24 Correct 0 ms 10808 KB Output is correct
25 Incorrect 0 ms 10808 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10808 KB Output is correct
2 Correct 0 ms 10808 KB Output is correct
3 Correct 0 ms 10808 KB Output is correct
4 Correct 0 ms 10808 KB Output is correct
5 Correct 0 ms 10808 KB Output is correct
6 Correct 0 ms 10808 KB Output is correct
7 Correct 0 ms 10808 KB Output is correct
8 Correct 0 ms 10808 KB Output is correct
9 Correct 0 ms 10808 KB Output is correct
10 Correct 0 ms 10808 KB Output is correct
11 Correct 0 ms 10808 KB Output is correct
12 Correct 0 ms 10808 KB Output is correct
13 Correct 0 ms 10808 KB Output is correct
14 Correct 0 ms 10808 KB Output is correct
15 Correct 0 ms 10808 KB Output is correct
16 Correct 0 ms 10808 KB Output is correct
17 Correct 0 ms 10808 KB Output is correct
18 Correct 0 ms 10808 KB Output is correct
19 Correct 0 ms 10808 KB Output is correct
20 Correct 0 ms 10808 KB Output is correct
21 Correct 0 ms 10808 KB Output is correct
22 Correct 0 ms 10808 KB Output is correct
23 Correct 0 ms 10808 KB Output is correct
24 Correct 0 ms 10808 KB Output is correct
25 Incorrect 0 ms 10808 KB Output isn't correct
26 Halted 0 ms 0 KB -