| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 602359 | APROHACK | Highway Tolls (IOI18_highway) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "grader.cpp"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ff first
#define ss second
using namespace std;
ll m, n, AA, BB, largo, e, subA, subB, largoA, largoB; //n = cities, m = edges
vector<pair<int, int> >adj[90000]; // nodo, indx
vector<int>w;
bool vis[100005];
bool test(int li, int pos, int ls){
for(int i = 0 ; i < m ; i++)w[i]=0;
for(int i = li ; i <= pos ; i++)w[i]=1;
//for(int i = pos+1 ; i < ls ; i++)w[i]=0;
if(ask(w) == largo*A )return false;
else return true;
}
void findE(){
int li=0, ls=m-1, pos=(m-1)/2;
while(li<ls){
pos = (li+ls)/2;
if(test(li, pos, ls))ls=pos;
else li=pos+1;
}
e = li;
}
void findSize(){
memset(vis, false, sizeof vis);
queue<int>nxt;
nxt.push(subA);
vis[subA]=true;
for(int i = 0 ; i < m ; i++)w[i]=0;
while(!nxt.empty()){
int cur = nxt.front();
nxt.pop();
for(int i = 0 ; i < adj[cur].size() ; i ++){
if(vis[adj[cur][i].ff] || adj[cur][i].ss == e)continue;
////cout<< " ll " << adj[cur][i].ff << endl;
vis[adj[cur][i].ff]=true;
w[adj[cur][i].ss]=1;
nxt.push(adj[cur][i].ff);
}
}
////cout<< ask(w)<<endl;
largoA = (ask(w)-largo)/(BB-AA);
nxt.push(subB);
for(int i = 0 ; i < m ; i++)w[i]=0;
memset(vis, false, sizeof vis);
vis[subB]=true;
while(!nxt.empty()){
int cur = nxt.front();
nxt.pop();
for(int i = 0 ; i < adj[cur].size() ; i ++){
if(vis[adj[cur][i].ff] || adj[cur][i].ss == e)continue;
////cout<<" ll " << adj[cur][i].ff << endl;
vis[adj[cur][i].ff]=true;
w[adj[cur][i].ss]=1;
nxt.push(adj[cur][i].ff);
}
}
memset(vis, false, sizeof vis);
////cout<< ask(w)<<endl;
largoB = (ask(w)-largo)/(BB-AA);
}
ll findNode(int start, int dist){
//cout << "finding " << start << " " << dist<<endl;
vector<int>posibilidades, nodoahi;
queue <pair<int, int> > q;
memset(vis, false, sizeof vis);
q.push({start, 0}); // nodo, dist
vis[start]=true;
while(!q.empty()){
pair<int , int> cur = q.front();
q.pop();
for(int i = 0 ; i < adj[cur.ff].size() ; i++){
if(vis[adj[cur.ff][i].ff] || adj[cur.ff][i].ss == e)continue;
if(cur.ss+1 == dist){
//cout<<"putin" << adj[cur.ff][i].ss << endl;
posibilidades.pb(adj[cur.ff][i].ss);
nodoahi.pb(adj[cur.ff][i].ff);
continue;
}
vis[adj[cur.ff][i].ff] = true;
//cout << "in" << adj[cur.ff][i].ff <<endl;
q.push({adj[cur.ff][i].ff, cur.ss+1});
}
}
if(!posibilidades.size())posibilidades.pb(e), nodoahi.pb(start);
//cout<< "pp \n";
//for(int i = 0 ; i < posibilidades.size() ; i ++ ) //cout<<posibilidades[i] << " ";
//cout << endl;
int li = 0, ls = posibilidades.size();
int pos = (li+ls)/2;
while(li<ls){
pos = (li+ls)/2;
for(int i = 0 ; i < m ; i ++)w[i]=0;
for(int i = li ; i <= pos ; i++)w[posibilidades[i]]=1;
if(ask(w)==largo){
li=pos+1;
}else{
ls = pos;
}
}
//cout<< " ans " << nodoahi[li] <<endl;
return nodoahi[li];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
n = N;
AA=A;
BB=B;
for(int i = 0 ; i < m ; i++){
adj[U[i]].pb({V[i], i});
adj[V[i]].pb({U[i], i} );
}
for (int i = 0; i < M; ++i) {
w.pb(0);
}
largo = ask(w) / A;
//cout<<"L"<<largo<<endl;
findE();
//cout<<e<<endl;
subA=U[e], subB=V[e];
findSize();
//cout<<largoA << " " << largoB << endl;
answer(findNode(subA, largoA), findNode(subB, largoB));
}