Submission #1062583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062583		uacoder123	Game (IOI14_game)	C++14	42 / 100	1042 ms	71504 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];
set<ii> s[1501];
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:s[b])
  {
    s[it.F].erase(mp(b,it.S));
    auto it1=s[a].lower_bound(mp(it.F,-1));
    s[(*it1).F].erase(mp(a,(*it1).S));
    ii f=mp(it.F,it.S+(*it1).S);
    s[a].erase(it1);
    s[a].insert(f);
    s[f.F].insert(mp(a,f.S));
  }
}
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)
{
  for(int i=0;i<n;++i)
  {
    par[i]=i;
    r[i]=1;
    for(int j=i+1;j<n;++j)
    {
      s[i].insert(mp(j,1));
      s[j].insert(mp(i,1));
    }
  }
}
int hasEdge(int u, int v)
{
  int pu=find(u),pv=find(v);
  if(pu==pv)
    return 0;
  ii f=(*s[pu].lower_bound(mp(pv,-1)));
  if(f.S>1)
  {
    s[pu].erase(mp(pv,f.S));
    s[pv].erase(mp(pu,f.S));
    s[pu].insert(mp(pv,f.S-1));
    s[pv].insert(mp(pu,f.S-1));
    return 0;
  }
  s[pu].erase(mp(pv,1));
  s[pv].erase(mp(pu,1));
  mer(pu,pv);
  return 1;
}

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