| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1133744 | t9unkubj | 게임 (IOI14_game) | C++20 | 0 ms | 0 KiB |
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
template<class T,auto op,int extra>
struct base_dsu{
vector<int>par;
vector<T>data;
base_dsu(int n):par(n,-1){
static_assert(!extra,"e is needed");
}
base_dsu(int n,T e):par(n,-1),data(n,e){}
T& operator[](int i){
static_assert(extra,"No data");
return data[leader(i)];
}
int root(int x){
if(par[x]<0)return x;
else return par[x]=root(par[x]);
}
bool same(int x,int y){
return root(x)==root(y);
}
bool merge(int x,int y){
x=root(x);
y=root(y);
if(x==y)return false;
par[x]+=par[y];
par[y]=x;
return true;
}
int size(int x){
return -par[root(x)];
}
int leader(int x){
return root(x);
}
};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;
constexpr int N=1500;
dsu ds(N);
int cnt[N][N];
vc<int>edge[N];
void initialize(int n) {
}
int hasEdge(int u, int v) {
u=ds.root(u),v=ds.root(v);
assert(u!=v);
if(cnt[u][v]==ds.size(u)*ds.size(v)-1){
for(auto&x:edge[v]){
edge[u].push_back(ds.root(x));
cnt[u][ds.root(x)]++;
cnt[x][v]--;
cnt[x][u]++;
edge[x].push_back(u);
}
edge[u].push_back(v);
ds.merge(u,v);
return 1;
}else{
edge[u].push_back(v);
edge[v].push_back(u);
cnt[u][v]++,cnt[v][u]++;
return 0;
}
}
namespace judge{
void run(){
int n;
cin>>n;
rep(i,n*(n-1)/2){
int u,v;
cin>>u>>v;
dbg(hasEdge(u,v));
}
}
};
int main(){judge::run();}