# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
38904 |
2018-01-07T18:40:46 Z |
adamczh1 |
Game (IOI14_game) |
C++14 |
|
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);
return 1;
}
if(!uf.findSet(u,v)){
uf.remaining[uf.root(u)]--;
uf.remaining[uf.root(v)]--;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
10808 KB |
Output is correct |
2 |
Incorrect |
0 ms |
10808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
10808 KB |
Output is correct |
2 |
Incorrect |
0 ms |
10808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
10808 KB |
Output is correct |
2 |
Incorrect |
0 ms |
10808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |