이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAXN=1510;
int n,U,V,pai[MAXN],prof[MAXN],q[MAXN][MAXN];
void initialize(int n)
{
for(int i=0;i<n;i++)
{
pai[i]=i;
for(int j=i+1;j<n;j++)
q[i][j]=1, q[j][i]=1;
}
}
int fd(int v)
{
if(v==pai[v]) return v;
return pai[v]=fd(pai[v]);
}
void join(int a,int b)
{
a=fd(a); b=fd(b);
if(a==b) return;
if(prof[a]>prof[b]) swap(a,b);
for(int i=0;i<n;i++)
q[b][i]+=q[a][i], q[i][b]+=q[i][a];
pai[a]=b;
if(prof[a]==prof[b]) prof[b]++;
}
int hasEdge(int u,int v)
{
int U=fd(u), V=fd(v);
// printf("\n\nQ[1][2] = %d\n\n",q[1][2]);
if(U==V){/*printf("BLABLA\n");*/ return 0; }
if(q[U][V]>1 || q[V][U]>1)
{
// printf("pai[%d] = %d pai[%d] = %d\n",u,U,v,V);
// printf("q = %d q = %d\n",q[U][V],q[V][U]);
q[U][V]--; q[V][U]--;
return 0;
}
join(u,v);
// printf("q = %d q = %d\n",q[U][V],q[V][U]);
return 1;
}
/*
int main ()
{
scanf("%d",&n);
initialize(n);
for(int i=0;i<n*(n-1)/2;i++)
{
scanf("%d %d",&U,&V);
printf("%d\n\n",hasEdge(U,V));
}
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |