# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
933823 | kim | 통행료 (IOI18_highway) | C++17 | 159 ms | 11720 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using pii=pair<int,int>;
#define f first
#define s second
using ti3=tuple<int,int,int>;
vector<int> adj1[90005],adj2[90005];
bitset<90005> vis;
int pre[90005];
vector<int> ans,tmp;
int dist;
int play(int n,vector<int> &U,vector<int> &V,int u0){
// for(int i=0;i<n;++i) adj2[i].clear();
vis=0;
int m=U.size();
{
int id=0;
queue<int> q;
q.emplace(u0);
vis[u0]=1;
pre[u0]=0;
while(q.size()){
int u=q.front(); q.pop();
for(auto &v:adj1[u]){
if(vis[v]) continue;
vis[v]=1;
q.emplace(v);
// adj2[u].eb(v);
// adj2[v].eb(u);
pre[v]=++id;
}
}
}
// {
// stack<pii> st;
// st.emplace(u0,u0);
// int id=-1;
// while(st.size()){
// auto [u,p]=st.top(); st.pop();
// pre[u]=++id;
// for(auto &v:adj2[u]){
// if(v!=p) st.emplace(v,u);
// }
// }
// }
int l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
for(int i=0;i<m;++i){
if(pre[U[i]]<=mid&&pre[V[i]]<=mid) tmp[i]=0;
else tmp[i]=1;
}
if(ask(tmp)==dist) r=mid;
else l=mid+1;
}
cerr<<pre[0]<<" "<<pre[1]<<" "<<pre[2]<<" "<<pre[3]<<'\n';
for(int i=0;i<n;++i){
if(pre[i]==l){
ans.eb(i);
return i;
}
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
for(int i=0;i<U.size();++i){
adj1[U[i]].eb(V[i]);
adj1[V[i]].eb(U[i]);
}
tmp.assign((int)U.size(),0);
dist=ask(tmp);
play(N,U,V,play(N,U,V,0));
answer(ans[0],ans[1]);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |