Submission #609422

#	Time	Username	Problem	Language	Result	Execution time	Memory
609422		MohamedAliSaidane	Highway Tolls (IOI18_highway)	C++14	12 / 100	144 ms	27608 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];
    int max_d = 1;
    void dfs(int x, int p = 0)
    {
        d[x] = d[p]  + 1;
        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);
            }
        }
    }
    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;
        int rep = 2;
        vi w(m, 0);
        ll norm = ask(w);
        while(debut <= fin)
        {
            int mid=  (debut + fin)/2;
            w.assign(m, 0);
            for(auto e: cor[mid])
            {
                w[top[e]] = 1;
            }
            ll cb =ask(w);
            if(cb > norm)
            {
                rep = mid;
                debut = mid + 1;
            }
            else
                fin = mid - 1;
        }
        debut = 0;
        fin = (int)(cor[rep].size()) - 1;
        int t = 0;
        while(debut <= fin)
        {
            int mid =(debut + fin)/2;
            w.assign(m, 0 );
            for(int i = debut; i <= mid;i  ++)
                w[top[cor[rep][i]]] = 1;
            ll cb = ask(w);
            if(cb > norm)
            {
                t= mid;
                fin = mid - 1;
            }
            else
            {
                debut = mid + 1;
            }
        }
        answer(0, cor[rep][t]);

    }

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