Submission #919085

#	Time	Username	Problem	Language	Result	Execution time	Memory
919085		velislavgarkov	Highway Tolls (IOI18_highway)	C++14	5 / 100	87 ms	11764 KiB

highway

#include "highway.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
vector <pair <int,int> > v[MAXN], dist;
vector <int> w;
int edge;
long long path;
int n;
long long a, b;
void find_tree(int x, int par) {
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (i.first==par) continue;
        w[i.second]=1;
        find_tree(i.first,x);
    }
}
void dfs(int x, int par, int d) {
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (i.first==par) continue;
        if (d==1) {
            dist.push_back(i);
            continue;
        }
        dfs(i.first,x,d-1);
    }
}
int find_one(int start) {
    for (int i=0;i<n-1;i++) w[i]=0;
    find_tree(start,start);
    int d=(ask(w)-path)/(b-a);
    if (d==0) return start;
    if (!dist.empty()) dist.clear();
    dfs(start,start,d);
    int l, r, mid;
    l=0; r=dist.size()-1;
    while (l<r) {
        mid=(l+r)/2;
        for (int i=0;i<n-1;i++) w[i]=0;
        for (int i=l;i<=mid;i++) w[dist[i].second]=1;
        int cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    return dist[l].first;
}
void find_pair (int N, vector <int> U, vector <int> V, int A, int B) {
    n=N; a=A; b=B;
    w.resize(n-1);
    for (int i=0;i<n-1;i++) {
        v[U[i]].push_back({V[i],i});
        v[V[i]].push_back({U[i],i});
    }
    for (int i=0;i<n-1;i++) w[i]=0;
    path=ask(w);
    //cout << path << endl;
    int l, r, mid;
    l=0; r=n-1;
    while (l<r) {
        mid=(l+r)/2;
        for (int i=0;i<n-1;i++) w[i]=0;
        for (int i=l;i<=mid;i++) w[i]=1;
        int cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    edge=l;
    //cout << U[edge] << ' ' << V[edge] << endl;
    int ans1, ans2;
    ans1=find_one(U[edge]);
    ans2=find_one(V[edge]);
    answer(ans1,ans2);    
}

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