제출 #586437

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586437		jasmin	통행료 (IOI18_highway)	C++14	0 / 100	230 ms	262144 KiB

highway

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

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

void answer(int s, int t){
    cout << "answer: " << s << " " << t << "\n";
}*/

void dfs(int v, int d, vector<vector<int> >& adi, vector<vector<int> >& con, vector<pair<int,int> >& p, vector<int>& c, int dist){
    if(d==dist){
        c.push_back(v);
    }

    //cout << v << " " << d << " " << p[v].first << " " << p[v].second << "\n";

    for(int i=0; i<(int)adi[v].size(); i++){
        int u=adi[v][i];
        int ind=con[v][i];

        if(u!=p[v].first){
            p[u]={v, ind};
            dfs(u, d+1, adi, con, p, c, dist);
        }
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b){
    int m=u.size();
    vector<vector<int> > adi(n, vector<int>(0));
    vector<vector<int> > con(n, vector<int>(0));
    for(int i=0; i<m; i++){
        //cout << i << ": " << u[i] << " " << v[i] << "\n";
        adi[u[i]].push_back(v[i]);
        adi[v[i]].push_back(u[i]);
        con[u[i]].push_back(i);
        con[v[i]].push_back(i);
    }

    /*for(auto x: adi){
        for(auto e: x){
            cout << e << " ";
        }
        cout << "\n";
    }*/

    vector<int> w(m, 0);
    int64_t dist=ask(w)/(int64_t)a;

    vector<int> canditate;
    vector<pair<int,int> > p(n, {-1, -1});
    dfs(0, 0, adi, con, p, canditate, dist);
    int l=0; int r=canditate.size()-1;
    int ans=0;
    dist*=a;
    while(l<=r){
        int m=l+(r-l)/2;
        //cout << l << " " << r << " " << m << "\n";

        w.assign(n, 0);
        for(int i=0; i<=m; i++){
            int c=canditate[i];
            w[p[c].second]=1;
        }

        int64_t resp=ask(w);
        //cout << resp << " " << dist << "\n";
        if(resp!=dist){
            ans=m;
            r=m-1;
        }
        else{
            l=m+1;
        }
        //cout << "=> " << l << " " << r << "\n";
    }

    answer(0, canditate[ans]);
}

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

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

    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