| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 70373 | top34051 | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 500 + 5;
const int maxm = 250000 + 5;
int n,m;
pii e[maxm];
int head[maxn];
vector<pii> way[maxn], edge[maxn];
int ban[maxm], res[maxm];
vector<int> tree;
int h[maxn], par[maxn], rec[maxn];
vector<int> p;
int cut[maxm];
int ask(int x, int y) {
for(auto &id : tree) if(id==x) id = y;
ask_count++;
if(ask_count > 8000) assert(0);
int ret = count_common_roads(tree);
for(auto &id : tree) if(id==y) id = x;
return ret;
}
void dfs(int u, int last, int lid) {
h[u] = h[last] + 1;
par[u] = last;
rec[u] = lid;
for(auto t : way[u]) {
int v = t.X, id = t.Y;
if(v==last) continue;
dfs(v,u,id);
}
}
void lca(int u, int v) {
if(u==v) return ;
if(h[u] >= h[v]) {
p.push_back(rec[u]);
lca(par[u],v);
}
else lca(v,u);
}
int findhead(int x) {
if(x==head[x]) return x;
return head[x] = findhead(head[x]);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
n = N; m = U.size();
for(int i=0;i<n;i++) head[i] = i;
for(int i=0;i<m;i++) {
int u = U[i], v = V[i];
e[i] = {u,v};
if(findhead(u)!=findhead(v)) {
head[findhead(u)] = findhead(v);
way[u].push_back({v,i});
way[v].push_back({u,i});
tree.push_back(i);
ban[i] = 1;
res[i] = -1;
}
else {
edge[u].push_back({v,i});
edge[v].push_back({u,i});
}
}
dfs(0,-1,-1);
int ori = ask(-1,-1);
for(int i=0;i<m;i++) {
if(ban[i]) continue;
int u = e[i].X, v = e[i].Y, wow = i;
p.clear();
lca(u,v);
int good = 0;
for(auto id : p) if(res[id]==-1) good = 1;
if(!good) continue;
int x = -1;
for(auto id : p) if(res[id]!=-1) x = id;
if(x==-1) {
for(auto id : p) cut[id] = ask(id,wow);
for(auto id : p) if(cut[id] - ori == 1) res[wow] = 1;
for(auto id : p) res[id] = ori - cut[id] + res[wow];
}
else {
res[wow] = ask(x,wow) - ori + res[x];
for(auto id : p) if(res[id]==-1) res[id] = ori - ask(id,wow) + res[wow];
}
}
for(int i=0;i<m;i++) {
if(res[i] == -1) res[i] = 1;
// if(ban[i]) printf("%d %d : %d\n",e[i].X,e[i].Y,res[i]);
}
for(int x=0;x<n;x++) {
while(1) {
int l = 0, r = edge[x].size()-1, mid, pos = -1;
while(l<=r) {
mid = (l+r)/2;
int val = 0;
vector<int> vec;
for(int i=0;i<n;i++) head[i] = i;
for(int i=0;i<=mid;i++) {
int v = edge[x][i].X, id = edge[x][i].Y;
head[findhead(x)] = findhead(v);
vec.push_back(id);
val -= res[id];
}
for(auto id : tree) {
int u = e[id].X, v = e[id].Y;
if(findhead(u)!=findhead(v)) {
head[findhead(u)] = findhead(v);
vec.push_back(id);
val -= res[id];
}
}
ask_count++;
if(ask_count > 8000) assert(0);
val += count_common_roads(vec);
if(val >= 1) {
pos = edge[x][mid].Y;
r = mid-1;
}
else l = mid+1;
}
if(pos==-1) break;
res[pos] = 1;
// printf("edge %d %d is good\n",e[pos].X,e[pos].Y);
}
}
vector<int> ans;
for(int i=0;i<m;i++) if(res[i]) ans.push_back(i);
return ans;
}