Submission #157109

#	Time	Username	Problem	Language	Result	Execution time	Memory
157109		InfiniteJest	Game (IOI14_game)	C++14	42 / 100	1051 ms	4960 KiB

game

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int N;
int k[1600];
int s[1600];
int p[1600][1600];

int find(int x){
  while(x!=k[x])x=k[x];
  return k[x];
}

bool same(int a, int b){
  return find(a)==find(b);
}

void unite(int a, int b){
  a=find(a);
  b=find(b);
  if(s[a]<s[b])swap(a,b);
  k[b]=a;
  s[a]+=s[b];
  //for(int i=0;i<n;i++)p[a][i]+=p[b][i];
}

void initialize(int n){
  N=n;
  for(int i=0;i<N;i++){
    k[i]=i;
    s[i]=1;
  }
}
int hasEdge(int u, int v){
  p[u][v]++;
  p[v][u]++;
  u=find(u);
  v=find(v);
  if(u==v)return 1;
  ll tot=0;
  for(int i=0;i<N;i++){
    if(find(i)==u){
      for(int y=0;y<N;y++){
        if(find(y)==v)tot+=p[i][y];
      }
    }
  }
  if(tot-1==s[u]*s[v]-1){
    unite(u,v);
    return 1;
  }
  return 0;
}

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