# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
306688 |
2020-09-26T06:55:30 Z |
tengiz05 |
Game (IOI14_game) |
C++17 |
|
1 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
int n;
int num_of_sets;
vector<int> rank;
vector<int> par;
vector<int> queries_asked;
vector<int> size;
void init(int _n){
n = _n;
num_of_sets = n;
par.assign(n, 0);
for(int i=0;i<n;i++)par[i] = i;
rank.assign(n, 0);
size.assign(n, 1);
queries_asked.assign(n, 0);
}
int root(int u){
if(par[u] == u)return u;
else return par[u] = root(par[u]);
}
bool is_same(int u, int v){
return (root(u) == root(v));
}
void merge(int u, int v){
u = root(u);
v = root(v);
if(u == v)return;
num_of_sets -- ;
if(rank[u] > rank[v]){
rank[u]++;
size[u] += size[v];
par[v] = u;
}else {
rank[v]++;
size[v] += size[u];
par[u] = v;
}
}
}s;
void initialize(int n) {
s.init(n);
}
int hasEdge(int u, int v) {
s.queries_asked[u]++;
s.queries_asked[v]++;
if(s.is_same(u, v)){
return 1;
}else {
if(s.num_of_sets == 2)return 0;
else if(s.queries_asked[u] == s.n-1 || s.queries_asked[v] == s.n-1){
s.merge(u, v);
return 1;
}else {
return 0;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |