Submission #660568

#	Time	Username	Problem	Language	Result	Execution time	Memory
660568		atigun	Game (IOI14_game)	C++11	100 / 100	499 ms	25248 KiB

game

#include<bits/stdc++.h>
#include"game.h"

using namespace std;
typedef long long ll;

struct DSU{
  vector<int> parent, size;
  int N;
  DSU(int n) : N(n){
    parent.resize(N);
    iota(parent.begin(), parent.end(), 0);
    size.resize(N, 1);
  }
  void reset(){
    size.assign(N, 1);
    iota(parent.begin(), parent.end(), 0);
  }
  int find(int v){
    return parent[v] = (parent[v]==v?v:find(parent[v]));
  }
  void merge(int v, int u){
    if(size[find(v)] < size[find(u)])
      swap(u, v);
    size[find(v)]+= size[find(u)];
    parent[find(u)] = find(v);
  }
};

const int maxn = 1500;
int n;
vector<vector<int>> S(maxn+5, vector<int>(maxn+5));
DSU dsu(maxn+5);

void initialize(int k){
  n = k;
  dsu.reset();
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      S[i][j] = (i!=j);
}

int hasEdge(int v, int u){
  if(dsu.find(v) == dsu.find(u)){
    return 0;
  } else if(S[dsu.find(v)][dsu.find(u)] == 1){
    vector<int> sums(n);
    for(int x = 0; x < n; x++)
      sums[dsu.find(x)] = S[dsu.find(x)][dsu.find(v)]+S[dsu.find(x)][dsu.find(u)];
    dsu.merge(u, v);
    for(int x = 0; x < n; x++)
      S[dsu.find(x)][dsu.find(v)] = S[dsu.find(v)][dsu.find(x)] = sums[dsu.find(x)];
    return 1;
  } else{
    S[dsu.find(v)][dsu.find(u)]--;
    S[dsu.find(u)][dsu.find(v)]--;
    return 0;
  }
}

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