# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
193138 | anubhavdhar | 게임 (IOI14_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<n;i++)
#define FORe(i,n) for(i=1;i<=n;i++)
#define FORr(i,a,b) for(i=a;i<b;i++)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first
#define ss second
#define cd complex<double>
#define vcd vector<cd>
using namespace std;
#include "game.h"
/*
const ll MAXN = 1511;//2e5+5;
const ll MOD = 1e9+7;
const ll ROOTN = 320;
const ll LOGN = 17;
const ll INF = 1e17 + 1101;
*/
int g[MAXN][MAXN],id[MAXN],sz[MAXN],N;
inline int root(int x)
{
while(x != id[x])
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}
/*
inline void DBG()
{
ll i;
FOR(i,N)
cout<<"id["<<i<<"] = "<<i<<endl;
}
*/
inline void mrg(int a,int b)
{
int i,x = root(a),y = root(b);
if(x != y)
{
if (sz[x] > sz[y])
swap(x,y);
id[x] = y;
sz[y] += sz[x];
sz[x] = 0;
FOR(i,N)
if(sz[i])
g[y][i] = g[i][y] = g[i][y] + g[i][x];
}
}
void initialize(int n)
{
N = n;
int i,j;
FOR(i,N)
{
id[i] = i;
sz[i] = 1;
FOR(j,N)
g[i][j] = 0;
}
//DBG();
}
int hasEdge(int u,int v)
{
int p = root(u),q = root(v);
if (p == q)
{
cout<<"DANGER";
return -1;
}
g[p][q]++;
g[q][p]++;
if (g[p][q] == sz[p]*sz[q])
{
mrg(p,q);
return 1;
}
return 0;
}
/*
inline void PlayGame(ll r)
{
ll a,b;
while(r--)
{
cin>>a>>b;
cout<<hasEdge(a,b)<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll n;
cin>>n;
initialize(n);
PlayGame((n*(n-1))/2);
return 0;
}*/