Submission #587255

#	Time	Username	Problem	Language	Result	Execution time	Memory
587255		jasmin	Highway Tolls (IOI18_highway)	C++14	0 / 100	11 ms	1780 KiB

highway

#include<bits/stdc++.h>
using namespace std;
#include<highway.h>

const int inf=1e9+7;

/*int64_t ask(vector<int> w){
    for(auto e: w){
        cout << e << " ";
    }
    cout << "\n" << flush;
    int64_t resp;
    cin >> resp;
    return resp;
}
void answer(int a, int b){
    cout << "answer: " << a << " " << b << "\n";
}*/

int find_edge(int m, int64_t dist){
    vector<int> w(m, 0);

    int l=0; int r=m-1;
    int ans=m-1;
    while(l<=r){
        //cout << "edge " << l << " " << r << "\n";
        int mi=l+(r-l)/2;
        w.assign(m, 0);
        for(int i=0; i<=mi; i++){
            w[i]=1;
        }
        int64_t resp=ask(w);
        if(resp!=dist){
            ans=mi;
            r=mi-1;
        }
        else{
            l=mi+1;
        }
    }
    return ans;
}

void dfs(int v, int d, vector<vector<int> >& adi, vector<bool>& vis, vector<int>& cand, int dist){
    if(vis[v]) return;
    vis[v]=true;

    if(d==dist){
        cand.push_back(v);
    }

    for(auto u: adi[v]){
        dfs(u, d+1, adi, vis, cand, dist);
    }
}

int find_node(vector<int>& cand, vector<vector<int> >& con, int m, int dist){
    vector<int> w(m, 0);
    int l=0; int r=cand.size()-1;
    int ans=r;
    while(l<=r){
        //cout << "node " << l << " " << r << "\n";
        int mi=l+(r-l)/2;
        w.assign(m, 0);
        for(int i=0; i<=mi; i++){
            for(auto x: con[cand[i]]){
                w[x]=1;
            }
        }
        int resp=ask(w);
        if(resp!=dist){
            ans=mi;
            r=mi-1;
        }
        else{
            l=mi+1;
        }
    }
    return cand[ans];
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B){
    int m=u.size();
    vector<int> w(m, 0);
    vector<int> cand;
    int64_t dist=ask(w); 
    int length=dist/(int64_t)A;

    int x=find_edge(m, dist);

    //cout << x << " " << u[x] << " " << v[x] << "\n";
    vector<bool> vis(n);
    vector<vector<int> > adi(n);
    vector<vector<int> > con(n);
    for(int i=0; i<m; i++){
        if(i==x) continue;
        adi[v[i]].push_back(u[i]);
        adi[u[i]].push_back(v[i]);

        con[v[i]].push_back(i);
        con[u[i]].push_back(i);
    }

    dfs(u[x], 0, adi, vis, cand, inf);
    w.assign(n, 0);
    for(int i=0; i<n; i++){
        if(!vis[i]) continue;
        //cout << "vis " << i << "\n";

        for(auto j: con[i]){
            w[j]=1;
        }
    }
    int length1=(ask(w)-dist)/(B-A);
    int length2=length-1-length1;

    //cout << "=> " << length1 << " " << length2 << "\n";

    vis.assign(n, false);
    cand.assign(0, 0);
    dfs(u[x], 0, adi, vis, cand, length1);
    /*for(auto e: cand){
        cout << "cand " << e << "\n";
    }*/
    int a=find_node(cand, con, m, dist);

    vis.assign(n, false);
    cand.assign(0, 0);
    dfs(v[x], 0, adi, vis, cand, length2);
    /*for(auto e: cand){
        cout << "cand " << e << "\n";
    }*/
    int b=find_node(cand, con, m, dist);
    
    answer(a, b);
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> u(m);
    vector<int> v(m);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        u[i]=a;
        v[i]=b;
    }
    int A, B;
    cin >> A >> B;
    find_pair(n, u, v, A, B);
}*/

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