oj.uz

Submission #1018338

# Submission time Handle Problem Language Result Execution time Memory
1018338 2024-07-09T19:09:37 Z vjudge1 Highway Tolls (IOI18_highway) C++17
12 / 100
 202 ms 262144 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 1 ms 3684 KB Output is correct
3 Correct 1 ms 3672 KB Output is correct
4 Correct 1 ms 3672 KB Output is correct
5 Correct 1 ms 3672 KB Output is correct
6 Correct 1 ms 3672 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct
8 Correct 1 ms 3672 KB Output is correct
9 Correct 1 ms 3672 KB Output is correct
10 Correct 1 ms 3672 KB Output is correct
11 Correct 2 ms 3672 KB Output is correct
12 Correct 1 ms 3672 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3672 KB Output is correct
2 Correct 7 ms 4368 KB Output is correct
3 Correct 69 ms 10480 KB Output is correct
4 Correct 65 ms 10536 KB Output is correct
5 Correct 71 ms 10524 KB Output is correct
6 Correct 60 ms 10264 KB Output is correct
7 Correct 63 ms 10324 KB Output is correct
8 Correct 72 ms 10480 KB Output is correct
9 Correct 65 ms 10608 KB Output is correct
10 Correct 61 ms 10540 KB Output is correct
11 Correct 69 ms 11760 KB Output is correct
12 Correct 77 ms 12332 KB Output is correct
13 Correct 76 ms 11800 KB Output is correct
14 Correct 78 ms 11228 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4952 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 198 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -