Submission #1018338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018338		vjudge1	통행료 (IOI18_highway)	C++17	12 / 100	202 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 9E4+16;
vii adj[MAXN];
ll dep[MAXN];
ll toPar[MAXN];

void dfs (ll u, ll par) {
    for (auto [v, id] : adj[u]) {
        if (v == par) continue;
        dep[v] = dep[u]+1;
        toPar[v] = id;
        dfs(v, u);
    }
}

void find_pair (int n, vi us, vi vs, int a, int b) {
    for (ll i = 0; i < us.size(); i++) {
        adj[us[i]].push_back({ vs[i], i });
        adj[vs[i]].push_back({ us[i], i });
    }
    dep[0] = 0;
    dfs(0, 0);
    ll rum = ask(vi(n-1, 0));
    assert(rum%a == 0);
    ll sdep = rum/a;
    vll cands;
    for (ll u = 0; u < n; u++) {
        if (dep[u] == sdep) cands.push_back(u);
    }
    ll l = 0, r = cands.size()-1;
    while (l < r) {
        ll mid = (l+r)>>1;
        vi vask(n-1, 0);
        for (ll i = l; i <= mid; i++) vask[toPar[cands[i]]] = 1;
        if (ask(vask) != sdep*a)
            r = mid;
        else
            l = mid+1;
    }
    answer(0, cands[l]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:25:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (ll i = 0; i < us.size(); i++) {
      |                    ~~^~~~~~~~~~~

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