Submission #784391

#	Time	Username	Problem	Language	Result	Execution time	Memory
784391		qwerasdfzxcl	Game (IOI14_game)	C++17	0 / 100	8 ms	468 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];
    }
  }
}dsu;
 
void initialize(int N) {
  n = N;
  dsu.init(n);
}
 
int hasEdge(int u, int v) {
  ++u, ++v;
  return dsu.merge(u, v);
}

Compilation message (stderr)

game.cpp: In member function 'int DSU::merge(int, int)':
game.cpp:37:3: warning: control reaches end of non-void function [-Wreturn-type]
   37 |   }
      |   ^

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