oj.uz

Submission #917023

# Submission time Handle Problem Language Result Execution time Memory
917023 2024-01-27T02:03:26 Z 12345678 Highway Tolls (IOI18_highway) C++17
6 / 100
 140 ms 15968 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;
pair<int, int> id[nx], ans;
vector<int> qrs, used;
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]=1;
    used.push_back(l);
    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.push_back(idx), 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;
    for (int i=0; i<m; i++) qrs[i]=1;
    while (nl<nr)
    {
        int md=(nl+nr+1)/2;
        for (int i=0; i<m; i++) if (used[i]) qrs[i]=0;
        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++) if (used[i]) qrs[i]=0;
        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);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5148 KB Output is correct
2 Correct 1 ms 5144 KB Output is correct
3 Correct 1 ms 5152 KB Output is correct
4 Correct 2 ms 5152 KB Output is correct
5 Correct 1 ms 5152 KB Output is correct
6 Incorrect 2 ms 5152 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5196 KB Output is correct
2 Correct 11 ms 6360 KB Output is correct
3 Correct 89 ms 13720 KB Output is correct
4 Correct 98 ms 13772 KB Output is correct
5 Correct 88 ms 13736 KB Output is correct
6 Correct 93 ms 13728 KB Output is correct
7 Correct 84 ms 13728 KB Output is correct
8 Correct 97 ms 13784 KB Output is correct
9 Correct 89 ms 13904 KB Output is correct
10 Correct 94 ms 13716 KB Output is correct
11 Correct 100 ms 14412 KB Output is correct
12 Incorrect 99 ms 14660 KB Output is incorrect: {s, t} is wrong.
13 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6376 KB Output is correct
2 Correct 17 ms 7192 KB Output is correct
3 Correct 26 ms 8440 KB Output is correct
4 Correct 77 ms 14960 KB Output is correct
5 Correct 73 ms 15020 KB Output is correct
6 Correct 90 ms 15492 KB Output is correct
7 Correct 74 ms 15968 KB Output is correct
8 Correct 73 ms 15096 KB Output is correct
9 Correct 67 ms 15324 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 11 ms 5968 KB Output is correct
3 Correct 71 ms 11828 KB Output is correct
4 Correct 101 ms 13716 KB Output is correct
5 Correct 94 ms 13720 KB Output is correct
6 Correct 88 ms 13900 KB Output is correct
7 Correct 88 ms 13956 KB Output is correct
8 Correct 93 ms 13712 KB Output is correct
9 Correct 140 ms 13488 KB Output is correct
10 Correct 74 ms 13824 KB Output is correct
11 Correct 120 ms 14588 KB Output is correct
12 Correct 95 ms 14800 KB Output is correct
13 Incorrect 100 ms 14484 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6004 KB Output is correct
2 Incorrect 14 ms 6164 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6252 KB Output is correct
2 Incorrect 11 ms 6184 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -