Submission #609577

#	Time	Username	Problem	Language	Result	Execution time	Memory
609577		MohamedAliSaidane	Highway Tolls (IOI18_highway)	C++14	0 / 100	75 ms	29264 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;
        }
        int t = cor[d_t][t_idx];
        /// 12 Queries for depth of t, 12 queries for t
        /// 12 Queries for LCA, 12 queries for depth of s
        /// 12 Queries for s
        /// Sum = 12 * 5 =  60
        int cur = t;
        vi ancs;
        while(cur != 0)
        {
            cur = sp[cur][0];
            ancs.pb(cur);
        }
        reverse(all(ancs));
        debut= 1;
        fin = (int)(ancs.size()) - 1;
        int lca = 0;
        while(debut <= fin)
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            int pr = ancs[mid];
            w[top[pr]] = 1;
            ll cb = ask(w);
            if(cb == norm)
            {
                lca = pr;
                debut = mid + 1;
            }
            else
                fin = mid -1;
        }
        for(auto e: ancs)
        {
            if(d[e] > d[lca])
            {
                dfs1(e);
                break;
            }
        }
        for(int i = 1; i <= max_d; i++)
            cor[i].clear();
        for(int i = 0; i < n;i ++)
        {
            if(interd.count(i) == 0)
            {
                cor[d[i]].pb(i);
            }
        }
        debut=  2;
        fin = max_d;
        int d_s = 1;
        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 u = ask(w);
            if(u > norm)
            {
                d_s = mid;
                debut = mid + 1;
            }
            else
                fin = mid  - 1;
        }
        debut = 0;
        fin = (int)(cor[d_s].size()) - 1;
        int s_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_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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31