Submission #714454

#	Time	Username	Problem	Language	Result	Execution time	Memory
714454		victor_gao	통행료 (IOI18_highway)	C++17	90 / 100	316 ms	17216 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii>g[90015];
vector<ll>all[90015],root[2];
vector<int>qry,ord;
ll n,m,mn,a,b,d,fa[90015],dep[90015];
ll S=6,T=13;
void bfs(int root){
    for (int i=0;i<=n;i++){
        fa[i]=0; dep[i]=0;
        all[i].clear(); ord.clear();
    }
    queue<int>q; q.push(root);
    dep[root]=1;
    all[1].push_back(root);
    while (!q.empty()){
        int p=q.front(); q.pop();
        ord.push_back(p);
        for (auto [i,idx]:g[p]){
            if (!dep[i]){
                dep[i]=dep[p]+1; fa[i]=idx;
                all[dep[i]].push_back(i);
                q.push(i);
            }
        }
    }
}
void solve1(int u){
    fill(qry.begin(),qry.end(),1);
    bfs(u);
    int l=0,r=ord.size()-1;
    while (l<r){
        int mid=(l+r)>>1;
        for (int i=1;i<=mid;i++)
            qry[fa[ord[i]]]=0;
        ll dis=ask(qry);
        if (dis==mn) r=mid;
        else l=mid+1;
        for (int i=1;i<=mid;i++)
            qry[fa[ord[i]]]=1;
    }
    int s=ord[l];
 //   cout<<"find "<<s<<'\n';
    fill(qry.begin(),qry.end(),1);
    bfs(s);
    l=0; r=ord.size()-1;
    while (l<r){
        int mid=(l+r)>>1;
        for (int i=1;i<=mid;i++)
            qry[fa[ord[i]]]=0;
        ll dis=ask(qry);
        if (dis==mn) r=mid;
        else l=mid+1;
        for (int i=1;i<=mid;i++)
            qry[fa[ord[i]]]=1;
    }
    int t=ord[l];
 //   cout<<"answer "<<s<<" "<<t<<'\n';
    answer(s,t);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n=N; m=U.size(); a=A; b=B;
    for (int i=0;i<m;i++){
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }
    qry.resize(m,0);
    mn=ask(qry); d=mn/A;
    int l=0,r=m-1,u,v;
    while (l<r){
        int mid=(l+r)>>1;
        for (int i=0;i<=mid;i++)
            qry[i]=1;
        ll now=ask(qry);
        /*
        cout<<"query : ";
        for (int i=0;i<m;i++)
            cout<<qry[i];
        cout<<" -> "<<now<<'\n';
        */
        for (int i=0;i<=mid;i++)
            qry[i]=0;
        if (now!=mn) r=mid;
        else l=mid+1;
    }
    u=U[l]; v=V[l];
  //  cout<<"solve "<<u<<" "<<v<<'\n';
    solve1(u);
}
/*
./rand
./highway
15 36 1 2 13 6
1 0
2 1
3 0
4 1
5 3
6 5
7 1
8 2
9 5
10 9
11 5
12 8
13 1
14 7
3 9
4 5
7 14
3 1
1 4
2 8
11 7
12 0
10 13
10 4
14 7
6 9
12 2
6 2
0 14
3 6
11 9
14 3
8 2
11 8
0 6
4 1

*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:75:21: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   75 |     int l=0,r=m-1,u,v;
      |                     ^

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