Submission #436185

#	Time	Username	Problem	Language	Result	Execution time	Memory
436185		healme	Highway Tolls (IOI18_highway)	C++14	100 / 100	370 ms	13784 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define X first
#define Y second
#define pb push_back
const int MAX=2e5+3;
using ii = pair < int , int >;
vector < int > pr[MAX];
int d[MAX],D[MAX];
int C[MAX];
queue < int > Q;
void bfs(int v){
    memset(d,-1,sizeof d);
    Q.push(v);d[v]=0;
    while(!Q.empty()){
        int p = Q.front();Q.pop();
        for(int u:pr[p]) if(d[u]==-1){
            d[u]=d[p]+1;Q.push(u);
        }
    }
}
void BFS(int v){
    memset(D,-1,sizeof D);
    Q.push(v);D[v]=0;
    while(!Q.empty()){
        int p = Q.front();Q.pop();
        for(int u:pr[p]) if(D[u]==-1){
            D[u]=D[p]+1;Q.push(u);
        }
    }
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M = U.size();
    vector < int > w(M);
    for (int i = 0; i < M; ++i)
        w[i] = 0;
    long long res = ask(w);
    int b=1,e=M-1,sp=0;
    while(b<=e){
        int mi=b+e>>1;
        for(int i=0;i<M;i++)w[i]=(i<mi);
        ll temp=ask(w);
        if(temp==res){
            b=mi+1;sp=mi;
        }
        else
            e=mi-1;
    }
    for(int i=sp;i<M;i++){
        pr[U[i]].pb(V[i]);
        pr[V[i]].pb(U[i]);

    }
    int u=U[sp],v=V[sp];
    BFS(u);bfs(v);

    vector < ii > vec;
    for(int i=0;i<n;i++){
        if(d[i]-D[i]==1){
            vec.pb(ii(D[i],i));
        }
    }
    sort(vec.begin(),vec.end());
    int sz=vec.size();
    for(int i=0;i<sz;i++) C[vec[i].Y]=i;

    for(int i=0;i<sp;i++)w[i]=1;

    b=1,e=sz-1;int an=sz;
    while(b<=e){
        int mi=b+e>>1;
        for(int i=sp;i<M;i++)
            w[i]=(max(C[U[i]],C[V[i]])>=mi);
        ll temp=ask(w);
        if(temp==res){
            an=mi;e=mi-1;
        }
        else b=mi+1;

    }
    int ans1=vec[an-1].Y;

    vec.clear();
    for(int i=0;i<n;i++){
        if(D[i]-d[i]==1){
            vec.pb(ii(D[i],i));
        }
    }
    sort(vec.begin(),vec.end());
    sz=vec.size();
    memset(C,0,sizeof C);
    for(int i=0;i<sz;i++) C[vec[i].Y]=i;

    for(int i=0;i<sp;i++)w[i]=1;

    b=1,e=sz-1;an=sz;
    while(b<=e){
        int mi=b+e>>1;
        for(int i=sp;i<M;i++)
            w[i]=(max(C[U[i]],C[V[i]])>=mi);
        ll temp=ask(w);
        if(temp==res){
            an=mi;e=mi-1;
        }
        else b=mi+1;

    }
    int ans2=vec[an-1].Y;
    answer(ans1,ans2);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mi=b+e>>1;
      |                ~^~
highway.cpp:73:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mi=b+e>>1;
      |                ~^~
highway.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mi=b+e>>1;
      |                ~^~

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