Submission #805957

#	Time	Username	Problem	Language	Result	Execution time	Memory
805957		fatemetmhr	Highway Tolls (IOI18_highway)	C++17	100 / 100	216 ms	33748 KiB

highway

//  ~ Be Name Khoda ~  //
 
#include "highway.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;
 
vector <int> tok, adj[maxn5], v, u, ver[2], ed[2], jda[maxn5];
ll len, h[maxn5];
int m, q[maxn5], par[maxn5], kh[maxn5], gooded;
int kparid[maxn5], parid[maxn5], kpar[maxn5];
ll pas[2][maxn5];
bool mark[maxn5], good[maxn5];
 
void bfs(int rt){
    par[rt] = -1;
    memset(h, -1, sizeof h);
    int l = 0, r = 1;
    q[0] = rt;
    h[rt] = 0;
    while(l < r){
        int a = q[l++];
        for(auto id : adj[a]){
            int b = u[id] == a ? v[id] : u[id];
            if(h[b] != -1)
                continue;
            //cout << "here " << a << ' ' << b << ' ' << id << endl;
            q[r++] = b;
            par[b] = a;
            h[b] = h[a] + 1;
            parid[b] = id;
        }
    }
}
 
void dfs(int v, int ty){
    mark[v] = true;
    //cout << v << ' ' << par[v] << endl;
    for(auto id : jda[v]){
        int u = (::u[id]) == v ? (::v[id]) : (::u[id]);
        if(mark[u])
            continue;
        //cout << "in " << v << ' ' << u << ' ' << ty << endl;
        dfs(u, ty);
        ver[ty].pb(u);
        ed[ty].pb(id);
    }
}
 
ll get(int id, int ty){
    if(pas[ty][id] == -1){
        fill(all(tok), 1);
        tok[gooded] = false;
        for(auto u : ed[ty ^ 1])
            tok[u] = false;
        for(int i = id + 1; i < int(ed[ty].size()); i++)
            tok[ed[ty][i]] = false;
        pas[ty][id] = ask(tok);
    }
    return pas[ty][id];
}
 
 
void find_pair(int n, std::vector<int> U, std::vector<int> V, int a, int b){
    memset(pas, -1, sizeof pas);
    u = U;
    v = V;
    m = u.size();
    for(int i = 0; i < m; i++){
        adj[u[i]].pb(i);
        adj[v[i]].pb(i);
    }
    int lo = -1, hi = m;
    tok.resize(m);
    fill(all(tok), 0);
    len = ask(tok) / a;
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        fill(all(tok), 0);
        fill(tok.begin(), tok.begin() + mid + 1, 1);
        ll cost = ask(tok);
        if(cost == len * a)
            lo = mid;
        else
            hi = mid;
    }
    gooded = hi;
    //cout << "ok " << hi << ' ' << u[hi] << ' ' << v[hi] << endl;
    bfs(u[hi]);
    for(int i = 0; i < n; i++){
        kh[i] = h[i];
        kpar[i] = par[i];
        kparid[i] = parid[i];
    }
    bfs(v[hi]);
    for(int i = 0; i < n; i++){
        //cout << i << ' ' << kh[i] << ' ' << h[i] << ' ' << par[i] << ' ' << kpar[i] << endl;
        if(h[i] < kh[i] && par[i] != -1)
            jda[par[i]].pb(parid[i]);
        if(h[i] > kh[i] && kpar[i] != -1){
            //cout << "Pushing " << i << ' ' << kpar[i] << endl;
            jda[kpar[i]].pb(kparid[i]);
        }
    }
    int rt[2] = {u[hi], v[hi]};
    memset(mark, false, sizeof mark);
    //cout << rt[0] << ' ' << rt[1] << endl;
    dfs(rt[0], 0);
    dfs(rt[1], 1);
    /*
    for(int i = 0; i < n - 1; i++)
        //cout << ed[i] << ' ' << ver[i] << endl;
    //*/
    ////cout << "its " << hi << endl;
    lo = -1; hi = ed[0].size();
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        if(get(mid, 0) == len * a)
            lo = mid;
        else
            hi = mid;
    }
    int s = (hi == int(ed[0].size()) ? rt[0] : ver[0][hi]);
    //cout << lo << ' ' << hi << ' ' << ed[0].size() << ' ' << s << endl;
    lo = -1; hi = ed[1].size();
    while(hi - lo > 1){
        int mid = (lo + hi) >> 1;
        if(get(mid, 1) == len * a)
            lo = mid;
        else
            hi = mid;
    }
    int t = (hi == int(ed[1].size()) ? rt[1] : ver[1][hi]);
    //cout << t << ' ' << lo << ' ' << hi << ' ' << ed[1].size() << endl;
    answer(s, t); 
}
 
 
 
 
 
 
 
 
 
 
 

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