Submission #303910

#	Time	Username	Problem	Language	Result	Execution time	Memory
303910		Supersonic	Game (IOI14_game)	C++14	100 / 100	526 ms	23160 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int g;unordered_set<int> rp;
int c[1501];int ln[1501];int sz[1501];int e[1501][1501];
int f(int a){
  while(a!=ln[a])a=ln[a];
  return a;
}
void un(int c,int d,int n){
  if(sz[c]<sz[d])swap(c,d);
  sz[c]+=sz[d];ln[d]=c;rp.erase(d);
  for(auto i:rp){
    int k=f(i);
    e[c][k]=e[k][c]=(e[k][c]+e[k][d]);
  }
}
void initialize(int n) {
  g=n;
  for(int i=0;i<n;i++){ln[i]=i;rp.insert(i);}memset(sz,1,sizeof(sz));
  for(int i=0;i<n;i++)for(int j=0;j<n;j++)e[i][j]=1;
}

int hasEdge(int u, int v) {
    int cu=f(u),cv=f(v);
    if(e[cu][cv]==1){un(cu,cv,g);return 1;}
    e[cu][cv]--;e[cv][cu]--;
    return 0;
}

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