Submission #1062599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062599		uacoder123	Game (IOI14_game)	C++14	100 / 100	296 ms	25256 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef pair <ii,ii> iiii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int par[1501],r[1501];
int s[1501][1501],sz;
int find(int x)
{
  if(par[x]==par[par[x]]) return par[x];
  par[x]=find(par[x]); return par[x];
}
void m(int a,int b)
{
  for(auto it=0;it<sz;++it)
  {
    if(it==a||it==b)
      continue;
    s[it][b]=0;
    s[it][a]=0;
    s[a][it]+=s[b][it];
    s[it][a]=s[a][it];
  }
}
void mer(int a,int b)
{
  if(r[a]>=r[b])
  {
    par[b]=a;
    m(a,b);
    if(r[a]==r[b])
      r[a]++;
  }
  else
  {
    m(b,a);
    par[a]=b;
  }
}
void initialize(int n)
{
  sz=n;
  for(int i=0;i<n;++i)
  {
    par[i]=i;
    r[i]=1;
    for(int j=i+1;j<n;++j)
    {
      s[i][j]=1;
      s[j][i]=1;
    }
  }
}
int hasEdge(int u, int v)
{
  int pu=find(u),pv=find(v);
  if(pu==pv)
    return 0;
  int f=s[pu][pv];
  s[pu][pv]--;
  s[pv][pu]--;
  if(f>1)
    return 0;
  mer(pu,pv);
  return 1;
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58