Submission #917018

#	Time	Username	Problem	Language	Result	Execution time	Memory
917018		12345678	Highway Tolls (IOI18_highway)	C++17	51 / 100	156 ms	15400 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;
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]=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;
    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[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 7 1 2 2 7
0 1
0 5
5 6
5 4
4 7
1 3
1 2

*/

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