oj.uz

Submission #903567

# Submission time Handle Problem Language Result Execution time Memory
903567 2024-01-11T08:33:37 Z 12345678 Highway Tolls (IOI18_highway) C++17
12 / 100
 87 ms 9960 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
int id[nx], t, vs[nx], res[nx];
vector<pair<int, int>> d[nx];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    vector<int> qs(N-1);
    for (int i=0; i<U.size(); i++) d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i});
    ll length=ask(qs)/A;
    queue<int> q;
    q.push(0);
    vs[0]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (auto [v, idx]:d[u]) if (!vs[v]) res[t]=v, id[t++]=idx, vs[v]=1, q.push(v);
    }
    int l=0, r=N-1;
    while (l<r)
    {
        int md=(l+r)/2;
        for (int i=0; i<N-1; i++) qs[i]=0;
        for (int i=0; i<=md; i++) qs[id[i]]=1;
        if (ask(qs)/B==length) r=md;
        else l=md+1;
    }
    answer(0, res[l]);
}

/*
4 3 1 2 0 3
0 1
0 2
1 3
*/

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2848 KB Output is correct
2 Correct 9 ms 3400 KB Output is correct
3 Correct 73 ms 9252 KB Output is correct
4 Correct 79 ms 9624 KB Output is correct
5 Correct 78 ms 9960 KB Output is correct
6 Correct 77 ms 9036 KB Output is correct
7 Correct 76 ms 9440 KB Output is correct
8 Correct 81 ms 9028 KB Output is correct
9 Correct 87 ms 9424 KB Output is correct
10 Correct 63 ms 9256 KB Output is correct
11 Correct 75 ms 8668 KB Output is correct
12 Correct 68 ms 8900 KB Output is correct
13 Correct 80 ms 8432 KB Output is correct
14 Correct 70 ms 8664 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3300 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 2852 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 Incorrect 8 ms 3376 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3256 KB Incorrect
2 Halted 0 ms 0 KB -