Submission #990111

#	Time	Username	Problem	Language	Result	Execution time	Memory
990111		huutuan	Game (IOI14_game)	C++14	100 / 100	331 ms	19616 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

static const int N=1500, S=40;

static struct DSU{
   int n;
   vector<int> lab;
   void init(int _n){
      n=_n;
      lab.assign(n, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      u=find_set(u); v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
      }
   }
} dsu;

static int n;
static set<pair<int, int>> edge[N/S+10], edge2;
static int cnt[N/S+10][N/S+10];

void initialize(int n_) {
   n=n_;
   for (int i=0; i<n; ++i){
      for (int j=i+1; j<n; ++j){
         if (i/S==j/S){
            edge[i/S].emplace(i, j);
         }else{
            ++cnt[i/S][j/S];
         }
      }
   }
   for (int i=0; i<(n+S-1)/S; ++i) for (int j=i+1; j<(n+S-1)/S; ++j) edge2.emplace(i, j);
}

int hasEdge(int u, int v) {
   if (u>v) swap(u, v);
   if (u/S!=v/S){
      u/=S, v/=S;
      --cnt[u][v];
      if (cnt[u][v]) return 0;
      dsu.init((n+S-1)/S);
      edge2.erase({u, v});
      for (auto &i:edge2) dsu.union_sets(i.first, i.second);
      if (dsu.lab[dsu.find_set(0)]+(n+S-1)/S){
         edge2.emplace(u, v);
         return 1;
      }
      return 0;
   }
   int id=u/S;
   int size=min(n, id*S+S)-id*S;
   dsu.init(size);
   edge[id].erase({u, v});
   for (auto &i:edge[id]) dsu.union_sets(i.first-S*id, i.second-S*id);
   if (dsu.lab[dsu.find_set(0)]+size){
      edge[id].emplace(u, v);
      return 1;
   }
   return 0;
}

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