oj.uz

Submission #917016

# Submission time Handle Problem Language Result Execution time Memory
917016 2024-01-27T01:10:27 Z 12345678 Highway Tolls (IOI18_highway) C++17
0 / 100
 12 ms 6544 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;
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];
    vs[ls]=vs[rs]=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}), vs[v]=1, q.push(v);
    }
    id[0]={ls, l};
    dfs(ls);
    nl=0; nr=cnt;
    //for (int i=0; i<=cnt; i++) cout<<i<<' '<<id[i].first<<' '<<id[i].second<<'\n';
    while (nl<nr)
    {
        int md=(nl+nr+1)/2;
        for (int i=0; i<m; 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++) 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[nr].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
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5152 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5200 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6544 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 2 ms 5460 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 12 ms 6244 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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