Submission #609599

#	Time	Username	Problem	Language	Result	Execution time	Memory
609599		MohamedAliSaidane	Highway Tolls (IOI18_highway)	C++14	18 / 100	184 ms	29316 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

    using namespace std;

    typedef long long ll;

    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;

    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpi;
    typedef vector<pll> vpl;

    #define pb push_back
    #define popb pop_back
    #define all(x) (x).begin(),(x).end()

    #define ff first
    #define ss second

    const int nax = 9e4 + 4;
    vpi adj[nax];
    int n, m, a, b;
    int d[nax];
    vi cor[nax];
    int top[nax], sp[nax][20], tin[nax], tout[nax];
    int max_d = 1;
    int cureul = -1;
    /*
    ll ask(vi w)
    {
        return 0;
    }
    */
    void dfs(int x, int p = 0)
    {
        sp[x][0] = p;
        d[x] = d[p]  + 1;
        tin[x] = ++cureul;
        max_d = max(max_d, d[x]);
        cor[d[x]].pb(x);
        for(auto e: adj[x])
        {
            if(e.ff  != p)
            {
                top[e.ff] = e.ss;
                dfs(e.ff,x);
            }
        }
        tout[x] = cureul;
    }
    bool check_sub(int a, int b)
    {
        if(tin[a] >= tin[b] && tin[a] <= tout[b])
            return true;
        else
            return false;
    }
    void tle()
    {
        while(1)
        {

        }
    }
    unordered_set<int> interd;
    void dfs1(int x)
    {
        interd.insert(x);
        for(auto e: adj[x])
        {
            if(e.ff == sp[x][0])
                continue;
            if(interd.count(e.ff) != 0)
                continue;
            dfs(e.ff, x);
        }
    }
    void find_pair(int N, vi U, vi V, int A, int B)
    {
        n = N;
        m = U.size();
        for(int i = 0 ;  i < m; i++)
        {
            adj[U[i]].pb({V[i], i });
            adj[V[i]].pb({U[i], i });
        }
        dfs(0);
        int debut = 2;
        int fin = max_d;
        vi w(m, 0);
        ll norm = ask(w);
        int d_t = 2;
        while(debut <= fin )
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            for(int i = mid; i <= max_d; i ++)
            {
                for(auto e: cor[i])
                    w[top[e]] = 1;
            }
            ll cb =ask(w);
            if(cb > norm)
            {
                d_t = mid;
                debut = mid +1 ;
            }
            else
                fin = mid - 1;
        }
        debut  = 0;
        fin = (int)(cor[d_t].size()) - 1;
        int t_idx = 0;
        while(debut <= fin)
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            for(int i = 0; i <= mid; i ++)
                w[top[cor[d_t][i]]] = 1;
            ll cb = ask(w);
            if(cb > norm)
            {
                t_idx = mid;
                fin = mid - 1;
            }
            else
                debut = mid + 1;
        }
        w.assign(m, 0);
        int t = cor[d_t][t_idx];
        int cur = t;
        while(cur != 0)
        {
            w[top[cur]] = 1;
            cur=  sp[cur][0];
        }
        ll delt = ask(w) - norm;
        delt /= (ll)(B - A);
        int lca =t;
        int avlast = t;
        for(int i = 0; i < delt;  i ++)
        {
            avlast=  lca;
            lca= sp[lca][0];
        }
        for(int i=  1; i <= max_d; i++)
        {
            cor[i].clear();
        }
        for(int i  = 0 ; i < n; i++)
        {
            if(check_sub(i, lca))
            {
                if(!check_sub(i, avlast))
                {
                    cor[d[i]].pb(i);
                }
            }
        }
        int d_s = d[lca];
        debut = d[lca] + 1;
        fin = max_d;
        while(debut <= fin)
        {
            int mid= (debut + fin)/2;
            w.assign(m, 0);
            for(int i = mid; i<= fin; i ++)
                for(auto e: cor[i])
                    w[top[e]] = 1;
            ll cb = ask(w);
            if(cb > norm)
            {
                d_s = mid;
                debut = mid + 1;
            }
            else
                fin = mid - 1;
        }
        int s_idx = 0;
        debut = 0 ;
        fin = (int)(cor[d_s].size()) - 1;
        while(debut <= fin)
        {
            int mid=  (debut + fin)/2;
            w.assign(m, 0);
            for(int i = debut ; i <= mid; i ++)
                w[top[cor[d_s][i]]] = 1;
            ll cb  = ask(w);
            if(cb > norm)
            {
                s_idx = mid;
                fin = mid - 1;
            }
            else
                debut = mid + 1;
        }
        int s= cor[d_s][s_idx];
        answer(s,t);

    }

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