Submission #176338

#	Time	Username	Problem	Language	Result	Execution time	Memory
176338		FieryPhoenix	Game (IOI14_game)	C++11	42 / 100	1058 ms	840 KiB

game

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
#include "game.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

vector<int>rt,siz;
int N;
int u[1500001],v[1500001];
int c=0;

int root(int x){
  while (x!=rt[x]){
    rt[x]=rt[rt[x]];
    x=rt[x];
  }
  return x;
}

void merge(int a, int b){
  a=root(a);
  b=root(b);
  if (siz[a]>siz[b]){
    siz[a]+=siz[b];
    rt[b]=a;
  }
  else{
    siz[b]+=siz[a];
    rt[a]=b;
  }
}

void initialize(int N){
  for (int i=0;i<N;i++)
    rt.push_back(i);
  for (int i=0;i<N;i++)
    siz.push_back(1);
}

int hasEdge(int U, int V){
  u[c]=U;
  v[c]=V;
  c++;
  int C=c-1;
  if (root(u[C])==root(v[C]))
    return 0;
  pair<int,int>p=make_pair(root(u[C]),root(v[C]));
  if (p.first>p.second)
    swap(p.first,p.second);
  int match=0;
  for (int j=0;j<C;j++){
    pair<int,int>p2=make_pair(root(u[j]),root(v[j]));
    if (p2.first>p2.second)
      swap(p2.first,p2.second);
    if (p2==p)
      match++;
  }
  if (match+1==siz[p.first]*siz[p.second]){
    merge(u[C],v[C]);
    return 1;
  }
  else
    return 0;
}

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