Submission #933950

#	Time	Username	Problem	Language	Result	Execution time	Memory
933950		kim	Highway Tolls (IOI18_highway)	C++17	82 / 100	205 ms	24068 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second

int n,m;
pii edge[130005];
vector<pii> graph[90005];
vector<int> tmp,ans;
ll mn_ask,dist;
int vis[90005];
int tour[90005];

int solve1(int U){
    int id=0;
    queue<int> q;
    q.emplace(U);
    vis[U]=1;
    tour[U]=0;
    while(q.size()){
        int u=q.front(); q.pop();
        for(auto &[v,i]:graph[u]){
            if(vis[v]) continue;
            vis[v]=1;
            q.emplace(v);
            tour[v]=++id;
        }
    }
    int l=dist,r=id;
    while(l<r){
        int mid=l+r>>1;
        for(int i=0;i<m;++i){
            auto &[u,v]=edge[i];
            if(tour[u]<=mid&&tour[v]<=mid) tmp[i]=0;
            else tmp[i]=1;
        }
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    for(int i=0;i<n;++i){
        if(tour[i]==l){
            ans.eb(i);
            return i;
        }
    }
}
int solve2(int U){
    int id=0;
    queue<int> q;
    q.emplace(U);
    for(int i=0;i<n;++i) vis[i]=0;
    vis[U]=1;
    tour[U]=0;
    while(q.size()){
        int u=q.front(); q.pop();
        for(auto &[v,i]:graph[u]){
            if(vis[v]) continue;
            vis[v]=1;
            q.emplace(v);
            tour[v]=++id;
        }
    }
    int l=dist,r=id;
    while(l<r){
        int mid=l+r>>1;
        for(int i=0;i<m;++i){
            auto &[u,v]=edge[i];
            if(tour[u]<=mid&&tour[v]<=mid) tmp[i]=0;
            else tmp[i]=1;
        }
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    for(int i=0;i<n;++i){
        graph[i].clear();
        if(tour[i]==l) ans.eb(i);
    }
    for(int i=0;i<m;++i){
        auto &[u,v]=edge[i];
        if(tour[u]<=l&&tour[v]<=l) graph[u].eb(v,i),graph[v].eb(u,i);
    }
    return ans.back();
}
void solve3(int U){
    using A=tuple<int,bool>;
    queue<A> q;
    q.emplace(U,0);
    for(int i=0;i<n;++i) vis[i]=-1;
    vis[U]=0;
    vector<int> tmp2(tmp.size(),1);
    vector<pii> vec;
    while(q.size()){
        auto [u,ok]=q.front(); q.pop();
        for(auto &[v,id]:graph[u]){
            if(vis[v]!=-1) continue;
            bool ok2=ok|(v==ans[0]);
            vis[v]=vis[u]+1;
            if(vis[v]<dist) q.emplace(v,ok2), tmp2[id]=0;
            else if(vis[v]==dist&&ok2) vec.eb(v,id);
        }
    }
    int l=0,r=(int)vec.size()-1;
    while(l<r){
        int mid=l+r>>1;
        tmp=tmp2;
        for(int i=0;i<=mid;++i) tmp[vec[i].s]=0;
        if(ask(tmp)==mn_ask) r=mid;
        else l=mid+1;
    }
    ans.eb(vec[l].f);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n=N,m=U.size();
    for(int i=0;i<m;++i){
        edge[i]={U[i],V[i]};
        graph[U[i]].eb(V[i],i);
        graph[V[i]].eb(U[i],i);
    }
    tmp.assign(m,0);
    mn_ask=ask(tmp), dist=mn_ask/A;
    solve3(solve2(solve1(0)));
    answer(ans[1],ans[2]);
}
/*
15 15  99 100  9 10
0 1
1 3
3 5
5 7
7 9
9 11
11 13
13 14
14 12
12 10
10 8
8 6
6 4
4 2
2 0
*/

Compilation message (stderr)

highway.cpp: In function 'int solve1(int)':
highway.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve2(int)':
highway.cpp:69:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'void solve3(int)':
highway.cpp:108:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         int mid=l+r>>1;
      |                 ~^~
highway.cpp: In function 'int solve1(int)':
highway.cpp:20:16: warning: control reaches end of non-void function [-Wreturn-type]
   20 |     queue<int> q;
      |                ^

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