| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 999569 | amine_aroua | 자동 인형 (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define intt long long
#define pb push_back
#define forr(i , x , y) for(int i = x; i <= y;i++)
#define fore(i , n) for(int i = 0 ; i < n;i++)
#define forn(i ,x , y) for(int i = x ; i >= y;i--)
long long ask(const vector<int> &w);
void answer(int s, int t);
const int MAXN = 90001;
intt a , b;
int n;
vector<pair<int ,int>> adj[MAXN];
vector<int> zeros , ones;
intt val;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int go(int root)
{
vector<int> dist(n , n);
vector<bool> vis(n , 0);
dist[root] = 0;
queue<int> q;
q.push(root);
while(!q.empty())
{
int x = q.front();
q.pop();
if(vis[x])
continue;
vis[x] = 1;
for(auto [u , i] : adj[x])
{
if(dist[u] > dist[x] + 1)
{
dist[u] = dist[x] + 1;
q.push(u);
}
}
}
vector<pair<int ,int>> nds;
fore(i , n)
nds.pb({dist[i] , i});
sort(nds.rbegin() , nds.rend());
int l = 0 , r = (int)nds.size();
vector<int> asked = ones;
while(l + 1 < r)
{
int mid = (l + r)/2;
asked = ones;
forr(j , 0 , mid - 1) {
for(auto i : adj[nds[j].second])asked[i.second] = 0;
}
if(ask(asked) == val)
l = mid;
else
r = mid;
}
return nds[l].second;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
n = N;
a = A , b = B;
int m = (int)U.size();
zeros.assign(m , 0);
ones.assign(m , 1);
fore(i , N)adj[i].clear();
val = ask(ones);
fore(i , m)
{
adj[U[i]].pb({V[i] , i});
adj[V[i]].pb({U[i] , i});
}
int S = go(go(0));
answer(S , go(S));
}