Submission #672637

#	Time	Username	Problem	Language	Result	Execution time	Memory
672637		blue	Game (IOI14_game)	C++17	0 / 100	1 ms	212 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;

int n;



struct dsu
{
  vi par;
  vi st;
  
  dsu()
  {
    par = vi(1500, -1);
    st = vi(1500, 1);
    for(int i = 0; i < 1500; i++)
      par[i] = i;
  }
  
  int root(int u)
  {
    if(par[u] == u)
      return u;
    else
      return (par[u] = root(par[u]));
}
  
  void join(int u, int v)
  {
    u = root(u);
    v = root(v);
    if(u == v)
      return;
    
    if(st[u] < st[v])
      swap(u, v);
    
    par[v] = u;
    st[u] += st[v];
	}
};

dsu ds;
int comp;

void initialize(int n_)
{
  n = n_;
  comp = n;
}

int hasEdge(int u, int v)
{
  if(ds.root(u) == ds.root(v))
    return 1;
  else if(comp == 2)
    return 0;
  else
  {
    ds.join(u, v);
    comp--;
    return 1;
  }
}

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