Submission #1035619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035619		Ludissey	Highway Tolls (IOI18_highway)	C++14	51 / 100	453 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define int long long
#define all(x) (x).begin(), (x).end()
using namespace std;
vector<int> depth;
vector<pair<int,int>> parent;
vector<int> sz;
vector<vector<pair<int,int>>> child;
vector<vector<pair<int,int>>> neigh;
vector<vector<pair<int,int>>> neigh2;
vector<signed> aska;
int S=-1;
int M,N;
int shortest;
int totCount=0;
int prevP=0;
int getSIZE(int x){
    sz[x]=1;
    for (auto u : child[x])
    {
        sz[x]+=getSIZE(u.first);
    }
    return sz[x];
}
int find_centroid(int _x){
    int x = _x;
    int sizeT=sz[_x];
    while (true) {
        int c = -1;
        for (int i = 0; i < sz(child[x]); i++) {
            if (sz[child[x][i].first]>sizeT/2) c = child[x][i].first;
        }
        //if (sz[x]-1>sizeT/2&&parent[x].first!=-1) c = parent[x].first;
        if (c!=-1) x = c; 
        else break;
    }
    return x;
}
 
void reroot(int R){
    child.clear();
    parent.clear();
    child.resize(N);
    parent.resize(N);
    queue<pair<int,int>> q;
    q.push({R,-1});
    parent[R]={-1,-1};
    while(!q.empty()){
        int x=q.front().first,p=q.front().second; q.pop();
        for (auto u : neigh2[x])
        {
            if(u.first==p||u.first==-1) continue;
            child[x].push_back(u);
            parent[u.first]={x,u.second};
            q.push({u.first,x});
        }
    }
}
 
void colorSubtree(int x){
    aska[parent[x].second]=1;
    for (auto u : child[x])
    {
        colorSubtree(u.first);
    }
}
 
int findTree(int x){
    int l=0, r=sz(child[x])-1;
    aska.resize(M);
    int ans=-1;
    while(l<=r){
        for (int i = 0; i < M; i++) aska[i]=0;
        int mid=(l+r)/2;
        for (int i = 0; i <= mid; i++)
        {
            colorSubtree(child[x][i].first);
        }
        totCount++;
        if(ask(aska)>shortest){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
        
    }
    if(ans<0) {
        for (int i = 0; i < M; i++) aska[i]=0;
        if(parent[x].first>-1) {
            aska[parent[x].second]=1;
            if(ask(aska)>shortest){
                S=x;
                return S;
            }
            for (int i = 0; i < sz(neigh2[parent[x].first]); i++)
            {
                if(neigh2[parent[x].first][i].first==x){
                    neigh2[parent[x].first][i].first=-1;
                }
            }
            return prevP;
        }
        S=x;
        return S;
    }
    else{
        for (int i = 0; i < sz(neigh2[child[x][ans].first]); i++)
        {
            if(neigh2[child[x][ans].first][i].first==x){
                neigh2[child[x][ans].first][i].first=-1;
            }
        }
        return child[x][ans].first;
    }
}
 
void find_pair(signed n, std::vector<signed> U, std::vector<signed> V, signed A, signed B){
    M=sz(U);
    N=n;
    neigh.resize(N);
    neigh2.resize(N);
    child.resize(N);
    sz.resize(N);
    depth.resize(N);
    parent.resize(N);
    vector<signed> ep(M,0);
    shortest=ask(ep);
    int initDist=shortest/A;
    totCount=0;
    for (int i = 0; i < M; i++)
    {
        neigh[U[i]].push_back({V[i],i});
        neigh[V[i]].push_back({U[i],i});
        neigh2[U[i]].push_back({V[i],i});
        neigh2[V[i]].push_back({U[i],i});
    }
    int c=0;
    reroot(0);
    while(S<0){
        //cerr<<c<<"\n";
        prevP=c;
        getSIZE(c);
        int _c=find_centroid(c);
        _c=findTree(_c);
        c=_c;
        reroot(c);
        if(sz(child[c])==0) {
            S=c;
        }
    }
 
    vector<int> possible;
    queue<pair<int,int>> q;
    q.push({S,-1});
    child.clear();
    parent.clear();
    depth.clear();
    neigh.resize(N);
    child.resize(N);
    depth.resize(N);
    parent.resize(N);
    depth[S]=0;
    while(!q.empty()){
        int x=q.front().first,p=q.front().second; q.pop();
        if(depth[x]==initDist) possible.push_back(x);
        for (auto u : neigh[x])
        {
            if(u.first==p) continue;
            child[x].push_back(u);
            depth[u.first]=depth[x]+1;
            parent[u.first]={x,u.second};
            q.push({u.first,x});
        }
    }
    int l=0; int r=sz(possible)-1;
    while(l<r){
        int mid=(l+r)/2;
        vector<signed> w(M,0);
        for (int i = l; i <= mid; i++) { w[parent[possible[i]].second]=1; }
        if(ask(w)>shortest){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    answer(S,(int)possible[l]);
}

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