| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 745559 | almothana05 | 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 "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long , long long> >kinder[300000] , ka;
vector<long long>cent , ed;
long long sub[300000], vis[300000];
long long a , b , menge , cmp , comp ,numm , nummer , kind;
long long st , en , mid , mit;
long long centroid(long long x , long long f , long long n){
for(long long i = 0 ; i < kinder[x].size() ; i++){
kind = kinder[x][i].first;
if(vis[kind] != 2 &&kind != f && sub[kind] * 2 > n){
return centroid(kind , x , n);
}
}
for(long long i = 0 ; i < kinder[x].size() ; i++){
ed[kinder[x][i].second] = 1;
}
vis[x] = 2;
return x;
}
long long dfs(long long x){
vis[x] = 1;
sub[x] = 1;
for(long long i = 0 ; i < kinder[x].size() ; i++){
kind = kinder[x][i].first;
if(vis[kind] == 0){
sub[x] += dfs(kind);
}
}
return sub[x];
}
long long bis(long long x , long long y , long long z ,long long f , long long root){
for(long long i = 0 ; i <= y ; i++){
ed[kinder[root][i].second] = 1;
}
st = x ; en = y; mid = y;
while(st <= en){
mit = (st + en)/2;
while(mid > mit){
if(kinder[root][mid].first == f){
mid--;
continue;
}
ed[kinder[root][mid].second] = 0;
mid--;
}
while(mid <= mit){
if(kinder[root][mid].first == f){
mid++;
continue;
}
ed[kinder[root][mid].second] = 1;
mid++;
}
if(mid > mit){
mid--;
}
numm = ask(ed);
if(numm >= z){
en = mit - 1;
}
else{
st = mit + 1;
}
}
return st;
}
long long suche(long long x){
dfs(x);
numm = centroid(x ,x , sub[x]);
// cout << x << ' '<<numm << "\n";
long long fater,pl;
for(long long i = 0 ; i < kinder[numm].size() ; i++ ){
if(sub[kinder[numm][i].first] > sub[numm]){
fater = kinder[numm][i].first;
break;
}
}
cmp = ask(ed);
if(numm == x){
if(cmp == comp){
return numm;
}
else{
comp = cmp;
pl = bis(0 , kinder[numm].size() - 1 , cmp , fater , numm );
}
}
else{
if(cmp == comp){
return suche(x);
}
else if(cmp == comp + b - a){
return numm;
}
else{
comp = cmp;
pl = bis(0 , kinder[numm].size() - 1 , cmp , fater , numm );
}
}
return suche(kinder[numm][pl].first);
}
void finde(){
for(long long i = 0 ; i < menge ; i++){
if(vis[i] == 0){
ka.push_back({i , dfs(i)});
}
}
for(long long i = 0 ; i < ka.size() ; i++){
cent.push_back(centroid(ka[i].first , ka[i].first , ka[i].second));
}
for(long long i = 0 ; i < menge ; i++){
if(vis[i] == 1){
vis[i] = 0;
}
}
ka.clear();
comp = ask(ed);
if(comp > cmp){
st = 0 ; en = cent.size() - 2; mid = cent.size() - 1;
while(st <= en){
mit = (st + en)/2;
while(mid > mit){
for(long long i = 0 ; i < kinder[cent[mid]].size() ; i++){
ed[kinder[cent[mid]][i].second] = 0;
}
mid--;
}
while(mid <= mit){
for(long long i = 0 ; i < kinder[cent[mid]].size() ; i++){
ed[kinder[cent[mid]][i].second] = 1;
}
mid++;
}
if(mid > mit){
mid--;
}
numm = ask(ed);
if(numm == comp){
en = mit - 1;
}
else{
st = mit + 1;
}
}
long long root , er ,zw;
root = cent[st];
cent.clear();
er = bis(0 , kinder[root].size() - 1 , cmp +b -a , -1 , root);
// cout << er << "\n";
if(comp == cmp + b - a){
zw = root;
for(long long i = 0 ; i < kinder[root].size() ; i++){
ed[kinder[root][i].second] = 1;
}
}
else{
zw = bis(er , kinder[root].size() - 1 , comp , -1 , root);
// cout << zw << "\n";
for(long long i = 0 ; i < kinder[root].size() ; i++){
ed[kinder[root][i].second] = 1;
}
// cout << kinder[root][er].first << "\n";
zw = suche(kinder[root][zw].first);
}
er = suche(kinder[root][er].first);
answer(er , zw);
return;
}
cent.clear();
finde();
}
void find_pair(long long N, vector<long long> u, vector<long long> v, long long A, long long B) {
a = A;
b = B;
menge = N;
for(long long i = 0 ; i < u.size() ; i++){
kinder[u[i]].push_back({v[i] , i});
kinder[v[i]].push_back({u[i] , i});
ed.push_back(0);
}
cmp = ask(ed);
finde();
}