| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 290862 | davi_bart | 게임 (IOI14_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
set<int> p[1600];
int arc[42][42];
int rad,N;
//bool ricalcola=1;
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(42,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;
auto y=p[pos].lower_bound(rad*ga);
if(y==p[pos].end())continue;
while((*y)>=rad*ga && (*y)<rad*(ga+1)){
q.push(*y);
y++;
if(y==p[pos].end())break;
}
}
bool ok=1;
for(int i=0;i<rad;i++){
if(ga*rad+i>=N)break;
if(vis[i]==0){
ok=0;
break;
}
}
if(ok==0){
p[u].insert(v);
p[v].insert(u);
return 1;
}
return 0;
}
p[u].erase(v);
p[v].erase(u);
arc[ga][gb]--;
arc[gb][ga]--;
bool ok=0;
if(arc[ga][gb])ok=1;
vector<bool> vis(42,0);
queue<int> q;
q.push(ga);
while(!q.empty() && ok==0){
int pos=q.front();
q.pop();
if(pos==gb){
ok=1;
break;
}
if(vis[pos])continue;
vis[pos]=1;
arc[ga][pos]++;
for(int i=0;i<=((N-1)/rad);i++){
if(arc[pos][i]){
if(i==gb){
ok=1;
break;
}
if(vis[i]==0)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;
}