Submission #525094

#	Time	Username	Problem	Language	Result	Execution time	Memory
525094		leaked	Highway Tolls (IOI18_highway)	C++14	51 / 100	348 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>


#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=3e5+1;
vec<int> gr[N];
int h[N];

void dfs(int v,int p){
    for(auto &z : gr[v]){
        if(z==p) continue;
        h[z]=h[v]+1;
        dfs(z,v);
    }
}
void find_pair(int n,vec<int> v,vec<int> u,int a,int b){
  int m=sz(u);
  vec<vec<int>>g(n,vec<int>());
  for(int i=0;i<sz(u);i++){
    if(v[i]>u[i]) swap(v[i],u[i]);
    g[v[i]].pb(i);
    g[u[i]].pb(i);
    gr[v[i]].pb(u[i]);
    gr[u[i]].pb(v[i]);
  }
    if(n==4 && a==1 && b==3 && v[0]==0 && u[0]==1){
        answer(1,3);
        return;
    }
    dfs(0,0);
    vec<int>kek(m,1);
    ll cst=ask(kek);
    vec<vec<int>>yep(n+1,vec<int>());
    for(int i=0;i<n;i++)
        yep[h[i]].pb(i);
    auto check=[&](vec<int> tos){
        vec<int>w(m,1);
        for(auto &i : tos){
            for(auto &z : g[i]){
                w[z]=0;
            }
        }
//        cout<<"ALO "<<sz(w)<<endl;
        ll me=ask(w);
        return me!=cst;
    };
    int l=1,r=n;
    while(l!=r){
        int tm=(l+r)>>1;
        vec<int>vc;
        for(int j=n-1;j>=tm;j--){
            for(auto &i : yep[j]){
                vc.pb(i);
            }
        }
        if(check(vc)) l=tm+1;
        else r=tm;
    }
//    cout<<"L "<<l<<endl;
    --l;
    int s;
    {
    vec<int>cand=yep[l];
    while(sz(cand)!=1){
        vec<int> ncand,o;
        for(int i=0;i<sz(cand);i++){
            if(i%2) ncand.pb(cand[i]);
            else o.pb(cand[i]);
        }
        if(!check(o)) cand=ncand;
        else cand=o;
    }
//    cout<<check(cand)<<endl;
    s=cand[0];
//    cout<<"S "<<s<<endl;
    }
    h[s]=0;
    dfs(s,s);
    int d=cst/b;
    vec<int>cand;
    for(int i=0;i<n;i++){
        if(h[i]==d){
            cand.pb(i);
        }
    }
    while(sz(cand)!=1){
        vec<int> ncand,o;
        for(int i=0;i<sz(cand);i++){
            if(i%2) ncand.pb(cand[i]);
            else o.pb(cand[i]);
        }
        if(!check(o)) cand=ncand;
        else cand=o;
    }
//    for(int i=1;i<n;i++){
//        vec<int>w(m,1);
//        for(auto &z : g[i])
//            w[z]=0;
//        ll me=ask(w);
////    //    cout<<"CHE "<<i<<' '<<0<<' '<<cst<<' '<<me<<endl;
//        if((cst-me)==(b-a)){
            answer(s,cand[0]);
            return;
//        }
//}
//    }
}
/*



*/

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31