oj.uz

Submission #903572

# Submission time Handle Problem Language Result Execution time Memory
903572 2024-01-11T08:47:06 Z 12345678 Highway Tolls (IOI18_highway) C++17
51 / 100
 104 ms 10048 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], l, r, h;
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;
    stack<int> q;
    q.push(0);
    vs[0]=1;
    while (!q.empty())
    {
        int u=q.top();
        q.pop();
        for (auto [v, idx]:d[u]) if (!vs[v]) res[t]=v, id[t++]=idx, vs[v]=1, q.push(v);
    }
    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;
    }
    int h=res[l];
    t=0;
    for (int i=0; i<N; i++) vs[i]=0;
    q.push(h);
    vs[h]=1;
    while (!q.empty())
    {
        int u=q.top();
        q.pop();
        for (auto [v, idx]:d[u]) if (!vs[v]) res[t]=v, id[t++]=idx, vs[v]=1, q.push(v);
    }
    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(h, res[l]);
}

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

/*
6 5 1 2 2 4
0 1
0 2
1 3
1 5
5 4
*/

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 2800 KB Output is correct
3 Correct 1 ms 2804 KB Output is correct
4 Correct 1 ms 2816 KB Output is correct
5 Correct 1 ms 2804 KB Output is correct
6 Correct 1 ms 2804 KB Output is correct
7 Correct 1 ms 2808 KB Output is correct
8 Correct 1 ms 2812 KB Output is correct
9 Correct 1 ms 2808 KB Output is correct
10 Correct 1 ms 2812 KB Output is correct
11 Correct 1 ms 2808 KB Output is correct
12 Correct 1 ms 2808 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2864 KB Output is correct
2 Correct 9 ms 3416 KB Output is correct
3 Correct 89 ms 9228 KB Output is correct
4 Correct 92 ms 9440 KB Output is correct
5 Correct 84 ms 9196 KB Output is correct
6 Correct 93 ms 9664 KB Output is correct
7 Correct 87 ms 9184 KB Output is correct
8 Correct 76 ms 9432 KB Output is correct
9 Correct 96 ms 9452 KB Output is correct
10 Correct 83 ms 8972 KB Output is correct
11 Correct 99 ms 8428 KB Output is correct
12 Correct 91 ms 8900 KB Output is correct
13 Correct 99 ms 8644 KB Output is correct
14 Correct 104 ms 8424 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3296 KB Output is correct
2 Correct 17 ms 4048 KB Output is correct
3 Correct 21 ms 4900 KB Output is correct
4 Correct 66 ms 8664 KB Output is correct
5 Correct 73 ms 8880 KB Output is correct
6 Correct 61 ms 8656 KB Output is correct
7 Correct 66 ms 8420 KB Output is correct
8 Correct 73 ms 8660 KB Output is correct
9 Correct 68 ms 8584 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2844 KB Output is correct
2 Correct 10 ms 3400 KB Output is correct
3 Correct 66 ms 7860 KB Output is correct
4 Correct 92 ms 9200 KB Output is correct
5 Correct 86 ms 9460 KB Output is correct
6 Correct 84 ms 8972 KB Output is correct
7 Correct 78 ms 8980 KB Output is correct
8 Correct 90 ms 9188 KB Output is correct
9 Correct 85 ms 9420 KB Output is correct
10 Correct 85 ms 9216 KB Output is correct
11 Correct 101 ms 8888 KB Output is correct
12 Correct 94 ms 8660 KB Output is correct
13 Correct 96 ms 8904 KB Output is correct
14 Correct 94 ms 8428 KB Output is correct
15 Correct 95 ms 9204 KB Output is correct
16 Correct 81 ms 8968 KB Output is correct
17 Correct 103 ms 8884 KB Output is correct
18 Correct 93 ms 8664 KB Output is correct
19 Correct 89 ms 9436 KB Output is correct
20 Correct 92 ms 8440 KB Output is correct
21 Correct 68 ms 9756 KB Output is correct
22 Correct 69 ms 9748 KB Output is correct
23 Correct 85 ms 10048 KB Output is correct
24 Correct 73 ms 9588 KB Output is correct
25 Correct 79 ms 8692 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3416 KB Incorrect
2 Halted 0 ms 0 KB -