Submission #784392

#	Time	Username	Problem	Language	Result	Execution time	Memory
784392		qwerasdfzxcl	Game (IOI14_game)	C++17	100 / 100	290 ms	24464 KiB

game

#include "game.h"
#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
int n; 
 
struct DSU{
  int path[1515], cnt[1515][1515];
  void init(int n){
    for (int i=1;i<=n;i++){
      path[i] = i;
      for (int j=1;j<=n;j++) if (i!=j) cnt[i][j] = 1;
    }
  }
  
  int find(int s){
    if (s==path[s]) return s;
    return path[s] = find(path[s]);
  }
  
  int merge(int s, int v){
    s = find(s), v = find(v);
    assert(s!=v);
    if (cnt[s][v] > 1){
      cnt[s][v]--;
      cnt[v][s]--;
      return 0;
    }
    
    path[v] = s;
    for (int i=1;i<=n;i++) if (find(i)==i && i!=s){
      cnt[s][i] += cnt[v][i];
      cnt[i][s] = cnt[s][i];
    }
    
    return 1;
  }
}dsu;
 
void initialize(int N) {
  n = N;
  dsu.init(n);
}
 
int hasEdge(int u, int v) {
  ++u, ++v;
  return dsu.merge(u, v);
}

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