Submission #609428

#	Time	Username	Problem	Language	Result	Execution time	Memory
609428		MohamedAliSaidane	Highway Tolls (IOI18_highway)	C++14	6 / 100	140 ms	27540 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 = 0;
        int fin = n - 2;
        vi w(m, 0);
        ll norm = ask(w);
        int s, t;
        while(debut <= fin)
        {
            int mid = (debut + fin)/2;
            w.assign(m, 0);
            for(int i = 0; i <= mid; i ++)
                w[i] = 1;
            ll cb  = ask(w);
            if(cb > norm)
            {
                s = mid;
                fin = mid - 1;
            }
            else
                debut = mid + 1;
        }
        debut = 1;
        fin = n - 1;
        while(debut <= fin)
        {
            int mid =(debut + fin)/2;
            w.assign(m, 0);
            for(int i = n - 2;i >= mid - 1;i --)
                w[i] = 1;
            ll cb = ask(w);
            if(cb > norm)
            {
                t = mid;
                debut = mid + 1;
            }
            else
                fin = mid - 1;
        }
        answer(s,t);
    }

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:91:15: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |         answer(s,t);
      |         ~~~~~~^~~~~
highway.cpp:91:15: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]

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