Submission #176618

#	Time	Username	Problem	Language	Result	Execution time	Memory
176618		FieryPhoenix	Game (IOI14_game)	C++11	100 / 100	552 ms	25356 KiB

game

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "game.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

vector<int>rt,siz;
int N;
int queried[1501][1501];
int prevRoot[1501];

int root(int x){
  while (x!=rt[x]){
    rt[x]=rt[rt[x]];
    x=rt[x];
  }
  return x;
}

void merge(int a, int b){
  if (siz[a]<siz[b])
    swap(a,b);
  for (int i=0;i<N;i++){
    queried[a][i]+=queried[b][i];
    queried[i][a]+=queried[i][b];
  }
    
  siz[a]+=siz[b];
  rt[b]=a;
}

void initialize(int n){
  N=n;
  for (int i=0;i<n;i++)
    rt.push_back(i);
  for (int i=0;i<n;i++)
    siz.push_back(1);
  for (int i=0;i<n;i++)
    prevRoot[i]=i;
}

int MERGED;

int hasEdge(int U, int V){
  if (prevRoot[U]==prevRoot[V])
    return 0;
  prevRoot[U]=root(U);
  U=prevRoot[U];
  prevRoot[V]=root(V);
  V=prevRoot[V];
  if (U==V)
    return 0;
  queried[U][V]++;
  queried[V][U]++;
  if (queried[U][V]==siz[U]*siz[V]){
    MERGED++;
    if (MERGED>=N)
      assert(0);
    merge(U,V);
    return 1;
  }
  else
    return 0;
}

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