Submission #915413

#	Time	Username	Problem	Language	Result	Execution time	Memory
915413		biank	Highway Tolls (IOI18_highway)	C++14	100 / 100	202 ms	12496 KiB

highway

#include <bits/stdc++.h>
using namespace std;
#define SIZE(x) int(x.size())
#define forn(i,n) for(int i=0;i<int(n);i++)
#define pb push_back
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
ll ask(const vi &w);
void answer(int s, int t);
void find_pair(int n, vi u, vi v, int /*a*/, int /*b*/) {
    vector<vii> adj(n);
    int m=SIZE(u);
    forn(i,m) {
        adj[u[i]].pb({v[i],i});
        adj[v[i]].pb({u[i],i});
    }
    
    vi w(m,0);
    ll D=ask(w);
    
    int low=-1, high=m;
    while(high-low>1) {
        int mid=(low+high)/2;
        forn(i,m) w[i]=i<=mid;
        if(ask(w)!=D) high=mid;
        else low=mid;
    }
    
    int e=high;
    int start[2]={u[e],v[e]};
    vi d[2];
    forn(i,2) {
        d[i].assign(n,-1);
        queue<int> q;
        q.push(start[i]);
        d[i][start[i]]=0;
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            for(auto [y,__]:adj[x]) {
                if(d[i][y]==-1) {
                    q.push(y);
                    d[i][y]=d[i][x]+1;
                }
            }
        }
    }
    
    int ans[2];
    forn(i,2) {
        vi node(n,0), edge(m,-1), dist(n,-1);
        queue<int> q;
        int c=0;
        q.push(start[i]);
        dist[start[i]]=0;
        
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            for(auto [y,idx]:adj[x]) {
                if(d[i][y]<d[1-i][y] && dist[y]==-1) {
                    dist[y]=dist[x]+1;
                    node[c]=y;
                    edge[idx]=c++;
                    q.push(y);
                } else if((d[i][y]>=d[1-i][y] && idx!=e)||dist[y]==dist[x]+1) {
                    edge[idx]=n;
                }
            }
        }
        
        int lo=-1, hi=c;
        while(hi-lo>1) {
            int mid=(lo+hi)/2;
            forn(j,m) w[j]=edge[j]>=mid;
            if(ask(w)!=D) lo=mid;
            else hi=mid;
        }
        if(lo==-1) ans[i]=start[i];
        else ans[i]=node[lo];
    }
    
    answer(ans[0],ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:42:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |             for(auto [y,__]:adj[x]) {
      |                      ^
highway.cpp:62:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |             for(auto [y,idx]:adj[x]) {
      |                      ^

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