Submission #917024

#	Time	Username	Problem	Language	Result	Execution time	Memory
917024		12345678	Highway Tolls (IOI18_highway)	C++17	100 / 100	210 ms	16072 KiB

highway

#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 (auto x:used) qrs[x]=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 (auto x:used) qrs[x]=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);
}

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

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

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31