oj.uz

Submission #917019

# Submission time Handle Problem Language Result Execution time Memory
917019 2024-01-27T01:28:52 Z 12345678 Highway Tolls (IOI18_highway) C++17
51 / 100
 159 ms 16656 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
ll m, res, l, r, ls, rs, vs[nx], cnt, nl, nr, used[nx];
pair<int, int> id[nx], ans;
vector<int> qrs;
vector<pair<int, int>> d[nx], t[nx];
queue<int> q;

void dfs(int u)
{
    //printf("dfs %d\n", u);
    for (auto [v, idx]:t[u]) id[++cnt]={v, idx}, dfs(v);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    m=U.size();
    qrs.resize(U.size());
    for (int i=0; i<m; i++) qrs[i]=0, d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i});
    res=ask(qrs);
    l=0; r=m-1;
    while (l<r)
    {
        int md=(l+r)/2;
        for (int i=0; i<m; i++) qrs[i]=i>md;
        if (ask(qrs)!=res) l=md+1;
        else r=md; 
    }
    ls=U[l];
    rs=V[l];
    //cout<<"edge "<<ls<<' '<<rs<<'\n';
    vs[ls]=vs[rs]=used[l]=1;
    q.push(ls);
    q.push(rs);
    while (!q.empty())
    {
        auto u=q.front();
        q.pop();
        for (auto [v, idx]:d[u]) if (!vs[v]) t[u].push_back({v, idx}), used[idx]=1, vs[v]=1, q.push(v);
    }
    id[0]={ls, l};
    dfs(ls);
    nl=0; nr=cnt;
    while (nl<nr)
    {
        int md=(nl+nr+1)/2;
        for (int i=0; i<m; i++) qrs[i]=0;
        for (int i=0; i<m; i++) if (!used[i]) qrs[i]=1;
        for (int i=md; i<=nr; i++) qrs[id[i].second]=1;
        if (ask(qrs)!=res) nl=md;
        else nr=md-1;
    }
    ans.first=id[nl].first;
    id[0]={rs, l};
    cnt=0;
    dfs(rs);
    nl=0; nr=cnt;
    while (nl<nr)
    {
        int md=(nl+nr+1)/2;
        for (int i=0; i<m; i++) qrs[i]=0;
        for (int i=0; i<m; i++) if (!used[i]) qrs[i]=1;
        for (int i=md; i<=nr; i++) qrs[id[i].second]=1;
        if (ask(qrs)!=res) nl=md;
        else nr=md-1;
    }
    ans.second=id[nl].first;
    answer(ans.first, ans.second);
}

/*
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

8 9 1 2 2 7
0 1
0 5
5 6
5 4
4 7
1 3
1 2
2 6
1 5
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6828 KB Output is correct
2 Correct 10 ms 7500 KB Output is correct
3 Correct 95 ms 14212 KB Output is correct
4 Correct 92 ms 14220 KB Output is correct
5 Correct 88 ms 14468 KB Output is correct
6 Correct 130 ms 14220 KB Output is correct
7 Correct 101 ms 14216 KB Output is correct
8 Correct 93 ms 14708 KB Output is correct
9 Correct 89 ms 14448 KB Output is correct
10 Correct 89 ms 14212 KB Output is correct
11 Correct 102 ms 15160 KB Output is correct
12 Correct 116 ms 15320 KB Output is correct
13 Correct 135 ms 15408 KB Output is correct
14 Correct 119 ms 15480 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7696 KB Output is correct
2 Correct 28 ms 8624 KB Output is correct
3 Correct 25 ms 9856 KB Output is correct
4 Correct 74 ms 15684 KB Output is correct
5 Correct 69 ms 15828 KB Output is correct
6 Correct 71 ms 16112 KB Output is correct
7 Correct 81 ms 16492 KB Output is correct
8 Correct 77 ms 15828 KB Output is correct
9 Correct 85 ms 16008 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6832 KB Output is correct
2 Correct 10 ms 7496 KB Output is correct
3 Correct 75 ms 12820 KB Output is correct
4 Correct 88 ms 14680 KB Output is correct
5 Correct 119 ms 14456 KB Output is correct
6 Correct 105 ms 14228 KB Output is correct
7 Correct 80 ms 14212 KB Output is correct
8 Correct 124 ms 14220 KB Output is correct
9 Correct 87 ms 14220 KB Output is correct
10 Correct 84 ms 14472 KB Output is correct
11 Correct 91 ms 15420 KB Output is correct
12 Correct 88 ms 15300 KB Output is correct
13 Correct 123 ms 15416 KB Output is correct
14 Correct 102 ms 15236 KB Output is correct
15 Correct 83 ms 14240 KB Output is correct
16 Correct 103 ms 14708 KB Output is correct
17 Correct 93 ms 15176 KB Output is correct
18 Correct 93 ms 15212 KB Output is correct
19 Correct 88 ms 14428 KB Output is correct
20 Correct 98 ms 15608 KB Output is correct
21 Correct 65 ms 14436 KB Output is correct
22 Correct 69 ms 14420 KB Output is correct
23 Correct 75 ms 14212 KB Output is correct
24 Correct 77 ms 14224 KB Output is correct
25 Correct 95 ms 16068 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7528 KB Output is correct
2 Correct 12 ms 7560 KB Output is correct
3 Correct 105 ms 15060 KB Output is correct
4 Correct 101 ms 15080 KB Output is correct
5 Correct 142 ms 15976 KB Output is correct
6 Correct 149 ms 16184 KB Output is correct
7 Correct 142 ms 16192 KB Output is correct
8 Correct 159 ms 15948 KB Output is correct
9 Incorrect 123 ms 13464 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7524 KB Output is correct
2 Correct 13 ms 7560 KB Output is correct
3 Correct 99 ms 15552 KB Output is correct
4 Correct 115 ms 14984 KB Output is correct
5 Correct 110 ms 15096 KB Output is correct
6 Incorrect 147 ms 16656 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -