# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
395152 |
2021-04-27T22:51:54 Z |
jeroenodb |
Game (IOI14_game) |
C++14 |
|
1 ms |
308 KB |
#include "game.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct DSU{
vector<int> sz,parent, out;
int components;
DSU(int n) {
sz.assign(n,1);
components = n;
out.assign(n,n-1);
parent.resize(n);
iota(all(parent),0);
}
DSU(){}
void link(int a, int b) {
components--;
if(sz[a]<sz[b]) {
swap(a,b);
}
sz[a] = max(sz[a],sz[b]+1);
out[a] += out[b];
out[a]-=2;// both directions of this edge are gone
parent[b] = a;
}
bool unite(int a, int b) {
int pa = find(a),pb = find(b);
if(pa!=pb) link(pa,pb);
return pa!=pb;
}
int find(int a) {
if(a==parent[a]) return a;
return parent[a] = find(parent[a]);
}
};
DSU dsu;
void initialize(int n) {
dsu = DSU(n);
}
int hasEdge(int u, int v) {
int pu = dsu.find(u), pv = dsu.find(v);
if(dsu.out[pu]==1 or dsu.out[pv]==1) {
dsu.link(pu,pv);
return true;
} else {
dsu.out[pu]--;
dsu.out[pv]--;
return false;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |