Submission #243769

#	Time	Username	Problem	Language	Result	Execution time	Memory
243769		AlexPop28	Game (IOI14_game)	C++11	100 / 100	484 ms	25336 KiB

game

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

// ultima problema degeaba pe ziua de azi promit

using namespace std;

struct DSU {
  int n;
  vector<int> dad, sz;
  vector<vector<int>> edges;
  
  DSU(int n_) : n(n_), dad(n, -1), sz(n, 1), edges(n, vector<int>(n)) {}
  
  int Find(int node) {
    if (dad[node] == -1) return node;
    return dad[node] = Find(dad[node]);
  }
  
  bool Union(int x, int y) {
    x = Find(x), y = Find(y);
    ++edges[x][y], ++edges[y][x];
    
    if (sz[x] < sz[y]) swap(x, y);
    
    if (edges[x][y] != sz[x] * sz[y]) {
      return false;
    }
    sz[x] += sz[y];
    dad[y] = x;
    
    for (int i = 0; i < n; ++i) {
      if (i == x || i == y || dad[i] != -1) continue;
      edges[x][i] += edges[y][i];
      edges[i][x] += edges[i][y];
    }
    return true;
  }
};

DSU dsu(0);

void initialize(int n) {
  dsu = DSU(n);
}

int hasEdge(int u, int v) {
  return dsu.Union(u, v);
}

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