# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
302654 |
2020-09-19T02:05:32 Z |
dCoding |
Game (IOI14_game) |
C++17 |
|
1 ms |
384 KB |
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define F first
#define S second
const int MAXN = 1505;
int coredge[MAXN], deg[MAXN];
set<pair<int, int>> s;
int n, comps;
int root[MAXN], ranks[MAXN];
int findRoot(int node) {
if(root[node] == node) return node;
return root[node] = findRoot(root[node]);
}
bool sameComp(int u, int v) {
return findRoot(u) == findRoot(v);
}
bool unite(int u, int v) {
if(sameComp(u,v)) return false;
int r1 = root[u], r2 = root[v];
if(ranks[r1] > ranks[r2]) {
root[r2] = r1;
ranks[r1] += ranks[r2];
} else {
root[r1] = r2;
ranks[r2] += ranks[r1];
}
return true;
}
void initialize(int _n) {
n = _n;
comps = n;
for(int i=0;i<n;i++) s.insert({deg[i], i});
for(int i=0;i<n;i++) {
root[i] = i; ranks[i] = 1;
}
}
int hasEdge(int u, int v) {
++coredge[u]; ++coredge[v];
int topnode = s.begin()->S;
if(comps > 2) {
s.erase({deg[u],u});
s.erase({deg[v],v});
++deg[u]; ++deg[v];
s.insert({deg[u],u});
s.insert({deg[v],v});
unite(u,v); --comps;
return 1;
} else {
if(!(comps == 2 && !sameComp(u,v))) {
s.erase({deg[u],u});
s.erase({deg[v],v});
++deg[u]; ++deg[v];
s.insert({deg[u],u});
s.insert({deg[v],v});
unite(u,v); --comps;
return 1;
} else {
return 0;
}
}
}
Compilation message
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:45:6: warning: unused variable 'topnode' [-Wunused-variable]
45 | int topnode = s.begin()->S;
| ^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |