Submission #682082

#	Time	Username	Problem	Language	Result	Execution time	Memory
682082		t6twotwo	Game (IOI14_game)	C++17	100 / 100	447 ms	16072 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> p;
int find(int x) {
  return x == p[x] ? x : p[x] = find(p[x]);
}
vector<vector<int>> cnt, s;
void unite(int u, int v) {
  if (s[u].size() > s[v].size()) {
    swap(u, v);
  }
  for (int x : s[u]) {
    p[x] = v;
    s[v].push_back(x);
  }
  for (int i = 0; i < n; i++) {
    if (i == v) {
      continue;
    }
    cnt[i][v] += cnt[i][u];
    cnt[v][i] += cnt[u][i];
  }
}
void initialize(int _n) {
  n = _n;
  cnt = vector(n, vector<int>(n));
  s.resize(n);
  p.resize(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    s[i].push_back(i);
  }
}
int hasEdge(int u, int v) {
  int a = find(u);
  int b = find(v);
  int x = s[a].size();
  int y = s[b].size();
  if (cnt[a][b] + 1 == x * y) {
    unite(a, b);
    return 1;
  }
  cnt[a][b]++;
  cnt[b][a]++;
  return 0;
}

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