제출 #176476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
176476		FieryPhoenix	게임 (IOI14_game)	C++11	42 / 100	1057 ms	26440 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;
map<int,int>queried[1501];

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])
    swap(a,b);

  for (auto it:queried[b]){
    queried[a][it.first]+=it.second;
    queried[it.first][a]+=queried[it.first][b];
    //queried[it.first].erase(b);
  }
  //queried[b].clear();
    
  siz[a]+=siz[b];
  rt[b]=a;
}

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=root(U);
  V=root(V);
  if (U==V)
    return 0;
  queried[U][V]++;
  queried[V][U]++;
  if (queried[U][V]==siz[U]*siz[V]){
    merge(U,V);
    return 1;
  }
  else
    return 0;
}

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