oj.uz

Submission #917020

# Submission time Handle Problem Language Result Execution time Memory
917020 2024-01-27T01:37:52 Z 12345678 Highway Tolls (IOI18_highway) C++17
51 / 100
 177 ms 16636 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)
{
    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);
    }
    //cout<<"edge "<<ls<<' '<<rs<<'\n';
    //for (int i=0; i<m; i++) cout<<used[i]<<' ';
    //cout<<'\n';
    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);
}

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

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

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 6744 KB Output is correct
3 Correct 2 ms 6756 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6776 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6776 KB Output is correct
8 Correct 2 ms 6576 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct
11 Correct 2 ms 6744 KB Output is correct
12 Correct 1 ms 6776 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6824 KB Output is correct
2 Correct 11 ms 7348 KB Output is correct
3 Correct 91 ms 14428 KB Output is correct
4 Correct 98 ms 14224 KB Output is correct
5 Correct 88 ms 14212 KB Output is correct
6 Correct 86 ms 14220 KB Output is correct
7 Correct 92 ms 14212 KB Output is correct
8 Correct 89 ms 14476 KB Output is correct
9 Correct 94 ms 14472 KB Output is correct
10 Correct 92 ms 14216 KB Output is correct
11 Correct 100 ms 15156 KB Output is correct
12 Correct 95 ms 15316 KB Output is correct
13 Correct 123 ms 15444 KB Output is correct
14 Correct 108 ms 15224 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7628 KB Output is correct
2 Correct 30 ms 8696 KB Output is correct
3 Correct 37 ms 9840 KB Output is correct
4 Correct 63 ms 15936 KB Output is correct
5 Correct 70 ms 15780 KB Output is correct
6 Correct 73 ms 16128 KB Output is correct
7 Correct 67 ms 16280 KB Output is correct
8 Correct 74 ms 15824 KB Output is correct
9 Correct 75 ms 16124 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 7340 KB Output is correct
3 Correct 72 ms 12556 KB Output is correct
4 Correct 89 ms 14440 KB Output is correct
5 Correct 85 ms 14504 KB Output is correct
6 Correct 84 ms 14424 KB Output is correct
7 Correct 88 ms 14440 KB Output is correct
8 Correct 93 ms 14228 KB Output is correct
9 Correct 91 ms 14220 KB Output is correct
10 Correct 93 ms 14448 KB Output is correct
11 Correct 94 ms 15120 KB Output is correct
12 Correct 100 ms 15280 KB Output is correct
13 Correct 97 ms 15184 KB Output is correct
14 Correct 96 ms 15240 KB Output is correct
15 Correct 71 ms 14236 KB Output is correct
16 Correct 82 ms 14452 KB Output is correct
17 Correct 83 ms 15180 KB Output is correct
18 Correct 143 ms 15372 KB Output is correct
19 Correct 90 ms 14256 KB Output is correct
20 Correct 121 ms 15368 KB Output is correct
21 Correct 75 ms 14412 KB Output is correct
22 Correct 77 ms 14464 KB Output is correct
23 Correct 73 ms 14236 KB Output is correct
24 Correct 95 ms 14208 KB Output is correct
25 Correct 99 ms 16292 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7512 KB Output is correct
2 Correct 14 ms 7412 KB Output is correct
3 Correct 108 ms 14828 KB Output is correct
4 Correct 110 ms 15080 KB Output is correct
5 Correct 148 ms 16180 KB Output is correct
6 Correct 135 ms 16172 KB Output is correct
7 Correct 154 ms 15964 KB Output is correct
8 Correct 177 ms 15828 KB Output is correct
9 Incorrect 100 ms 13012 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 17 ms 7524 KB Output is correct
2 Correct 18 ms 7556 KB Output is correct
3 Correct 104 ms 14624 KB Output is correct
4 Correct 150 ms 14724 KB Output is correct
5 Correct 141 ms 15096 KB Output is correct
6 Incorrect 146 ms 16636 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -