Submission #348897

#	Time	Username	Problem	Language	Result	Execution time	Memory
348897		juggernaut	Highway Tolls (IOI18_highway)	C++14	90 / 100	805 ms	37756 KiB

highway

#include"highway.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
using namespace std;
vector<pair<int,int>>g[90005];
int h[90005],p[90005];
int n,m;
map<vector<int>,long long>mp;
long long o_ask(vector<int>v){
    if(mp.count(v))return mp[v];
    else return mp[v]=ask(v);
}
long long pivot;
int depth(int root){
    for(int i=0;i<n;i++)h[i]=0,p[i]=i;
    queue<int>q;
    int timer=0;
    q.push(root);
    h[root]=1;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(auto to:g[v])if(!h[to.first]){
            q.push(to.first);
            h[to.first]=h[v]+1;
        }
    }
    sort(p,p+n,[](int x,int y){return h[x]>h[y];});
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r)>>1;
        vector<int>v(m,0);
        for(int i=0;i<=mid;i++)
            for(auto to:g[p[i]])v[to.second]=1;
        if(o_ask(v)==pivot)l=mid+1;
        else r=mid;
    }
    return p[l];
}
void find_pair(int n,vector<int>x,vector<int>y,int a,int b){
    ::n=n;::m=x.size();
    pivot=o_ask(vector<int>(m,0));
    for(int i=0;i<m;i++){
        g[x[i]].push_back({y[i],i});
        g[y[i]].push_back({x[i],i});
    }
    int s=depth(depth(0));
    int t=depth(s);
    answer(s,t);
}
/*
5 4 1 2 0 4
0 1
0 2
1 3
1 4
*/

Compilation message (stderr)

highway.cpp: In function 'int depth(int)':
highway.cpp:19:9: warning: unused variable 'timer' [-Wunused-variable]
   19 |     int timer=0;
      |         ^~~~~

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