Submission #595372

#	Time	Username	Problem	Language	Result	Execution time	Memory
595372		TimDee	Highway Tolls (IOI18_highway)	C++14	11 / 100	232 ms	13004 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
void find_pair(int n,vector<int>u,vector<int>v,int a,int b) {
    int m=u.size();
    vector<int>scuza(m,1),amog,paiu;
    int dist=ask(scuza)/b;
    vector<int>d(n,0);
    vector<int>vis(n,0);
    vector<vector<pair<int,int>>>adj(n);
    for(int i=0;i<m;++i){
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
    }
    vis[0]=1;
    queue<int>q; q.push(0);
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for(auto it:adj[u]) {
            int v=it.first;
            if (!vis[v]) {
                vis[v]=1; d[v]=d[u]+1; q.push(v);
            }
        }
    }
    vector<vector<int>>D(n); for(int i=0;i<n;++i) D[d[i]].push_back(i);
    int l=0,r=n-1; while(l<r) {
        int mid=(l+r)>>1;
        paiu=scuza;
        for (int i=0;i<=mid;++i) for(auto u:D[i]) for(auto it:adj[u]) if(d[it.first]==d[u]-1) paiu[it.second]=0;
        int x=ask(paiu); if(x<dist*b) r=mid; else l=mid+1;
    } int s; if (r==0) s=0; else {
    amog=D[r]; int bgn;
    l=0,r=amog.size()-1; while(l<r) {
        int mid=(l+r)>>1;
        paiu=scuza;
        for(int i=l;i<=mid;++i) for(auto it:adj[amog[i]]) if(d[it.first]==d[amog[i]]-1) paiu[it.second]=0;
        int x=ask(paiu); if(x<dist*b) r=mid; else l=mid+1;
    } bgn=amog[r]; 
    vis.assign(n,0);
    for(auto it:adj[bgn]) if(d[it.first]+1==d[bgn]) vis[it.first]=1;
    vis[bgn]=1; q.push(bgn);
    d.assign(n,1e9); for(int i=0;i<n;++i) if(vis[i]) d[i]=-1; d[bgn]=0;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for(auto it:adj[u]) {
            int v=it.first;
            if(!vis[v]) {vis[v]=1; d[v]=d[u]+1; q.push(v);}
        }
    }
    D.assign(n,vector<int>(0));
    for(int i=0;i<n;++i) if(d[i]>=0 && d[i]!=1e9)D[d[i]].push_back(i);
    l=0,r=n-1;
    while (l<r) {
        int mid=(l+r)>>1;
        paiu=scuza;
        for(auto u:D[mid]) for(auto it:adj[u]) if(d[it.first]==d[u]+1) paiu[it.second]=0;
        int x=ask(paiu);if(x<b*dist) l=mid+1; else r=mid;
    }
    amog=D[r]; l=0,r=amog.size()-1;
    while(l<r) {
        int mid=(l+r)>>1;
        paiu=scuza;
        for(int i=l;i<=mid;++i) for(auto it:adj[amog[i]]) if(d[it.first]==d[amog[i]]-1) paiu[it.second]=0;
        int x=ask(paiu); if(x<b*dist) r=mid; else l=mid+1;
    }
    s=amog[r]; } 
    d.assign(n,0); vis.assign(n,0); vis[s]=1; 
    q.push(s);
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (auto it:adj[u]) {
            int v=it.first; if(!vis[v]) {vis[v]=1; d[v]=d[u]+1; q.push(v);}
        }
    }
    D.assign(n,vector<int>(0));
    for(int i=0;i<n;++i) D[d[i]].push_back(i);
    amog=D[dist]; l=0,r=amog.size()-1;
    while(l<r) {
        int mid=(l+r)>>1;
        paiu=scuza;
        for(int i=l;i<=mid;++i) for(auto it:adj[amog[i]]) if(d[it.first]==d[amog[i]]-1) paiu[it.second]=0;
        int x=ask(paiu); if(x<b*dist) r=mid; else l=mid+1;
    }
    int t=amog[r];
    answer(s,t);
}

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