Submission #799570

#	Time	Username	Problem	Language	Result	Execution time	Memory
799570		Khizri	Highway Tolls (IOI18_highway)	C++17	51 / 100	335 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1e5+5;
int n,m,a,b,mx,sz,dis;
vector<int>que;
vector<pii>vt[mxn];
vector<pii>nodes;
void find_dep(int u,int p,int dep){
    mx=max(mx,dep);
    for(pii pp:vt[u]){
        int v=pp.F;
        if(v!=p){
            find_dep(v,u,dep+1);
        }
    }
}
void dfs(int u,int p,int dep){
    for(pii pp:vt[u]){
        int v=pp.F,idx=pp.S;
        if(v==p) continue;
        if(dep+1<=sz){
            que[idx]=1;
        }
        else{
            que[idx]=0;
        }
        dfs(v,u,dep+1);
    }
}
void add_nodes(int u,int p,int dep){
    for(pii pp:vt[u]){
        int v=pp.F,idx=pp.S;
        if(v!=p){
            if(dep+1==dis) nodes.pb({v,idx});
            add_nodes(v,u,dep+1);
        }
    }
}
ll check(int x){
    sz=x;
    dfs(1,-1,0);
    ll res=ask(que);
    return res;
}
void find_pair(int N, vector<int> ux, vector<int> vx, int A, int B) {
    n=N;
    a=A,b=B;
    m=ux.size();
    for(int i=0;i<m;i++){
        int u=ux[i]+1,v=vx[i]+1;
        vt[u].pb({v,i});
        vt[v].pb({u,i});
    }
    for(int i=0;i<m;i++){
        que.pb(1);
    }
    ll cost=ask(que);
    find_dep(1,-1,0);
    int l=0,r=mx;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)<cost){
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    ll cost2=cost/b*a;
    dis=l;
    add_nodes(1,-1,0);
    l=0,r=nodes.size()-1;
    while(l<=r){
        int mm=(l+r)/2;
        for(int i=0;i<m;i++){
            que[i]=0;
        }
        for(int i=l;i<=mm;i++){
            que[nodes[i].S]=1;
        }
        ll res=ask(que);
        if(res>cost2){
            r=mm-1;
        }
        else{
            l=mm+1;
        }
    }
    r++;
    int root=nodes[r].F;
    ll cnt=cost/b;
    nodes.clear();
    dis=cnt;
    add_nodes(root,-1,0);
    l=0,r=nodes.size()-1;
    while(l<=r){
        int mm=(l+r)/2;
        for(int i=0;i<m;i++){
            que[i]=0;
        }
        for(int i=l;i<=mm;i++){
            que[nodes[i].S]=1;
        }
        ll res=ask(que);
        if(res>cost2){
            r=mm-1;
        }
        else{
            l=mm+1;
        }
    }
    r++;
    int root2=nodes[r].F;
    answer(root-1,root2-1);
}
/*
g++ highway.cpp grader.cpp ; .\a.exe
8 7 1 2 5 6
0 1
0 2
1 3
1 4
4 6
6 7
2 5
*/

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