제출 #290825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290825		davi_bart	게임 (IOI14_game)	C++14	15 / 100	85 ms	892 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ld long double
set<int> p[1600];
bool arc[42][42];
int rad;
void sist(int a,int b){
  bool ok=0;
  for(int i=rad*a;i<rad*(a+1);i++){
    for(int j=rad*b;j<rad*(b+1);j++){
      if(p[i].find(j)!=p[i].end())ok=1;
    }
  }
  arc[a][b]=arc[b][a]=ok;
}
int hasEdge(int u, int v) {
    int ga=u/rad,gb=v/rad;
    if(ga==gb){
      p[u].erase(v);
      p[v].erase(u);
      vector<bool> vis(50,0);
      queue<int> q;
      q.push(u);
      while(!q.empty()){
        int pos=q.front();
        q.pop();
        if(pos/rad!=ga)continue;
        if(vis[pos%rad])continue;
        vis[pos%rad]=1;
        for(int x:p[pos])q.push(x);
      }
      bool ok=1;
      for(int i=0;i<rad;i++)if(vis[i]==0)ok=0;

      if(ok==0){
        p[u].insert(v);
        p[v].insert(u);
        return 1;
      }
      return 0;
    }
    p[u].erase(v);
    p[v].erase(u);
    sist(ga,gb);
    vector<bool> vis(50,0);
    queue<int> q;
    q.push(ga);
    bool ok=0;
    while(!q.empty()){
      int pos=q.front();
      q.pop();
      if(pos==gb){
        ok=1;
        break;
      }
      if(vis[pos])continue;
      vis[pos]=1;
      for(int i=0;i<rad;i++){
        if(arc[pos][i]==1)q.push(i);
      }
    }
    if(ok==0){
      p[u].insert(v);
      p[v].insert(u);
      arc[ga][gb]=arc[gb][ga]=1;
      return 1;
    }
    return 0;
}
/*
4
0 3
1 0
0 2
3 1
1 2
2 3
*/
void initialize(int n){
  rad=min(40,n);
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      p[i].insert(j);
    }
  }
  for(int i=0;i<rad;i++){
    for(int j=0;j<rad;j++){
      arc[i][j]=1;
    }
  }
}

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