| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 158287 | kig9981 | 통행료 (IOI18_highway) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[90000];
int dist1[90000], dist2[90000];
bool chk[90000];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
int M=U.size(), S, T, s, e;
vector<int> W(M,0), C1, C2;
queue<pair<int,int>> Q;
long long D=ask(W);
for(int i=0;i<M;i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
s=0; e=N-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<M;i++) W[i]=i<=m;
if(ask(W)!=D) e=m-1;
else s=m+1;
}
memset(dist,0x7f,sizeof(dist));
dist[U[s]]=dist[V[s]]=0;
Q.emplace(0,U[s]);
Q.emplace(1,V[s]);
while(!Q.empty()) {
auto[v,c]=Q.front();
Q.pop();
(v ? C2:C1).push_back(c);
for(auto n: adj[c]) if(dist[n]>dist[c]+1) {
dist[n]=dist[c]+1;
Q.emplace(v,n);
}
}
s=0; e=C1.size()-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<N;i++) chk[i]=false;
for(int i=m;i<C1.size();i++) chk[C1[i]]=true;
for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
if(ask(W)!=D) s=m+1;
else e=m-1;
}
S=C1[e];
s=0; e=C2.size()-1;
while(s<=e) {
int m=(s+e)>>1;
for(int i=0;i<N;i++) chk[i]=false;
for(int i=m;i<C2.size();i++) chk[C2[i]]=true;
for(int i=0;i<M;i++) W[i]=chk[U[i]]^chk[V[i]];
if(ask(W)!=D) s=m+1;
else e=m-1;
}
T=C2[e];
answer(S,T);
}