Submission #1096275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096275		azberjibiou	Highway Tolls (IOI18_highway)	C++17	100 / 100	193 ms	25532 KiB

highway

#include "highway.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=300050;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
int N, M;
vector <int> adj[mxN];
vector <pii> E;
ll val0;
int S1, S2;
int dist[mxN][2];
int col[mxN];
vector <int> ct[2];
bool trash[mxN];
vector <int> par[mxN];
int ans[2];
void init(int n, vector <int> u, vector <int> v, int a, int b){
    N=n;
    M=u.size();
    for(int i=0;i<M;i++){
        int t1=u[i], t2=v[i];
        adj[t1].push_back(t2);
        adj[t2].push_back(t1);
        E.emplace_back(t1, t2);
    }
}
void find_edge(){
    vector <int> w(M), one(M);
    val0=ask(w);
    int s=0, e=M-1;
    while(s!=e){
        int mid=(s+e)/2;
        for(int i=0;i<M;i++) w[i]=((s<=i && i<=mid) ? 1 : 0);
        for(int i=0;i<M;i++) if(one[i]==1) w[i]=1;
        ll valb=ask(w);
        if(valb>val0) e=mid;
        else{
            for(int i=s;i<=mid;i++) one[i]=1;
            s=mid+1;
        }
    }
    S1=E[s].fi, S2=E[s].se;
}
void bfs(int st, int idx){
    for(int i=0;i<N;i++) dist[i][idx]=-1;
    queue <int> que;
    que.push(st);
    dist[st][idx]=0;
    while(que.size()){
        int now=que.front();
        que.pop();
        for(int x : adj[now]) if(dist[x][idx]==-1){
            dist[x][idx]=dist[now][idx]+1;
            que.push(x);
        }
    }
}
void classify_vertex(){
    for(int i=0;i<N;i++){
        if(dist[i][0]==dist[i][1]){
            col[i]=-1;
            continue;
        }
        if(dist[i][0]<dist[i][1]) ct[0].push_back(i), col[i]=0;
        else ct[1].push_back(i), col[i]=1;
    }
    for(int i=0;i<M;i++){
      	if(E[i]==pii(S1, S2) || E[i]==pii(S2, S1)) continue;
        int a=E[i].fi, b=E[i].se;
        if(col[a]==-1 || col[b]==-1 || col[a]!=col[b]){
            trash[i]=true;
            continue;
        }
        int c=col[a];
        if(dist[a][c]==dist[b][c]){
            trash[i]=true;
            continue;
        }
        if(dist[a][c]<dist[b][c]) swap(a, b);
        par[a].push_back(i);
    }
    for(int i=0;i<M;i++) if(E[i]==pii(S1, S2) || E[i]==pii(S2, S1)) par[S1].push_back(i), par[S2].push_back(i);
}
void find_vertex(int idx){
    sort(all(ct[idx]), [&](int a, int b){return dist[a][idx]>dist[b][idx];});
    int s=0, e=ct[idx].size()-1;
    while(s!=e){
        int mid=(s+e)/2;
        vector <int> w(M);
        for(int i=0;i<=mid;i++) for(int x : par[ct[idx][i]]) w[x]=1;
        for(int i=0;i<M;i++) if(trash[i]) w[i]=1;
        ll valw=ask(w);
        if(valw>val0) e=mid;
        else s=mid+1;
    }
    ans[idx]=ct[idx][s];
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
    init(n, U, V, A, B);
    find_edge();
    bfs(S1, 0);
    bfs(S2, 1);
    classify_vertex();
    find_vertex(0);
    find_vertex(1);
    answer(ans[0], ans[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