Submission #915406

#	Time	Username	Problem	Language	Result	Execution time	Memory
915406		biank	통행료 (IOI18_highway)	C++14	51 / 100	3089 ms	12108 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<int> vi;
typedef long long ll;
ll ask(const vi &w);
void answer(int s, int t);
const int MAXN = 90000;
int d[2][MAXN];
vector<ii> adj[MAXN];
int c=0;

void find_pair(int n, vi u, vi v, int /*a*/, int /*b*/) {
    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);
    
    auto bs=[&](int lo, int hi) {
        while(hi-lo>1) {
            int mid=(lo+hi)/2;
            forn(i,m) w[i]=i<=mid;
            if(ask(w)!=D) hi=mid;
            else lo=mid;
        }
        return hi;
    };
    
    int e=bs(-1,m);
    int start[2]={u[e],v[e]};
    memset(d,-1,sizeof d);
    forn(i,2) {
        queue<int> q;
        q.push(start[i]);
        int dist=0;
        while(!q.empty()) {
            int sz=SIZE(q);
            forn(_,sz) {
                int x=q.front();
                q.pop();
                d[i][x]=dist;
                for(auto [y,__]:adj[x]) {
                    if(d[i][y]==-1) q.push(y);
                }
            }
            dist++;
        }
    }
    
    int ans[2];
    forn(i,2) {
        vi node(n,0), edge(m,-1), dist(n,-1);
        queue<int> q;
        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:49:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |                 for(auto [y,__]:adj[x]) {
      |                          ^
highway.cpp:68:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |             for(auto [y,idx]:adj[x]) {
      |                      ^

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