Submission #292271

#	Time	Username	Problem	Language	Result	Execution time	Memory
292271		SamAnd	Highway Tolls (IOI18_highway)	C++17	51 / 100	299 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, m;
vector<int> g[N];
vector<int> gi[N];

int d[N];
int u[N];
void dfs0(int x, int p)
{
    if (x == p)
        d[x] = 0;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
        {
            u[x] = gi[x][i];
            continue;
        }
        d[h] = d[x] + 1;
        dfs0(h, x);
    }
}

void find_pair(int N_, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n = N_;
    m = sz(U);
    for (int i = 0; i < m; ++i)
    {
        int x = U[i];
        int y = V[i];
        g[x].push_back(y);
        g[y].push_back(x);
        gi[x].push_back(i);
        gi[y].push_back(i);
    }

    vector<int> v;
    v.assign(m, 0);
    int dd = ask(v) / A;

    dfs0(0, 0);
    int maxu = 0;
    for (int x = 0; x < n; ++x)
        maxu = max(maxu, d[x]);
    int l = 1, r = maxu;
    int ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        v.assign(m, 0);
        for (int x = 0; x < n; ++x)
        {
            if (d[x] >= mid)
            {
                v[u[x]] = 1;
            }
        }
        if (ask(v) != dd * 1LL * A)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    vector<int> t;
    for (int x = 0; x < n; ++x)
    {
        if (d[x] == ans)
        {
            t.push_back(x);
        }
    }
    int ans1;
    {
        int l = 0, r = sz(t) - 1;
        int ans;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            v.assign(m, 0);
            for (int i = 0; i <= mid; ++i)
            {
                v[u[t[i]]] = 1;
            }
            if (ask(v) != dd * 1LL * A)
            {
                ans = t[mid];
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        ans1 = ans;
    }

    dfs0(ans1, ans1);
    t.clear();
    for (int x = 0; x < n; ++x)
    {
        if (d[x] == dd)
        {
            t.push_back(x);
        }
    }
    int ans2;
    {
        int l = 0, r = sz(t) - 1;
        int ans;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            v.assign(m, 0);
            for (int i = 0; i <= mid; ++i)
            {
                v[u[t[i]]] = 1;
            }
            if (ask(v) != dd * 1LL * A)
            {
                ans = t[mid];
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        ans2 = ans;
    }
    answer(ans1, ans2);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs0(int, int)':
highway.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:143:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  143 |     answer(ans1, ans2);
      |     ~~~~~~^~~~~~~~~~~~
highway.cpp:143:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:84:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         if (d[x] == ans)
      |         ^~

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