| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 176334 | FieryPhoenix | Game (IOI14_game) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
vector<int>rt,siz;
int N;
int u[1500001],v[1500001];
int c=0;
int root(int x){
while (x!=rt[x]){
rt[x]=rt[rt[x]];
x=rt[x];
}
return x;
}
void merge(int a, int b){
a=root(a);
b=root(b);
if (siz[a]>siz[b]){
siz[a]+=siz[b];
rt[b]=a;
}
else{
siz[b]+=siz[a];
rt[a]=b;
}
}
void initialize(int N){
for (int i=0;i<N;i++)
rt.push_back(i);
for (int i=0;i<N;i++)
siz.push_back(1);
}
int hasEdge(int U, int V){
u[c]=U;
v[c]=V;
c++;
int C=c-1;
if (root(u[C])==root(v[C]))
return 0;
pair<int,int>p=make_pair(root(u[C]),root(v[C]));
if (p.first>p.second)
swap(p.first,p.second);
int match=0;
for (int j=0;j<C;j++){
pair<int,int>p2=make_pair(root(u[j]),root(v[j]));
if (p2.first>p2.second)
swap(p2.first,p2.second);
if (p2==p)
match++;
}
if (match+1==siz[p.first]*siz[p.second]){
merge(u[i],v[i]);
return 1;
}
else
return 0;
}