Submission #990100

#	Time	Username	Problem	Language	Result	Execution time	Memory
990100		huutuan	Game (IOI14_game)	C++14	42 / 100	1095 ms	9840 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

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]);
   }
   bool 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;
         return 1;
      }
      return 0;
   }
} dsu;

mt19937 rng(69420);

int n;
set<pair<int, int>> edge;
vector<pair<int, int>> spanning_tree;

bool build_spanning_tree(){
   dsu.init(n);
   vector<pair<int, int>> tmp(edge.begin(), edge.end());
   shuffle(tmp.begin(), tmp.end(), rng);
   vector<pair<int, int>> new_spanning_tree;
   for (auto &i:tmp) if (dsu.union_sets(i.first, i.second)) new_spanning_tree.push_back(i);
   if (dsu.lab[dsu.find_set(0)]==-n){
      sort(new_spanning_tree.begin(), new_spanning_tree.end());
      spanning_tree.swap(new_spanning_tree);
      return 1;
   }
   return 0;
}

void initialize(int n_) {
   n=n_;
   for (int i=0; i<n; ++i) for (int j=i+1; j<n; ++j){
      edge.emplace(i, j);
   }
   build_spanning_tree();
}

int hasEdge(int u, int v) {
   if (u>v) swap(u, v);
   edge.erase({u, v});
   if (binary_search(spanning_tree.begin(), spanning_tree.end(), make_pair(u, v))){
      int ans=build_spanning_tree();
      if (!ans){
         edge.emplace(u, v);
         return 1;
      }
      return 0;
   }
   return 0;
}

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