Submission #903572

#	Time	Username	Problem	Language	Result	Execution time	Memory
903572		12345678	통행료 (IOI18_highway)	C++17	51 / 100	104 ms	10048 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
int id[nx], t, vs[nx], res[nx], l, r, h;
vector<pair<int, int>> d[nx];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    vector<int> qs(N-1);
    for (int i=0; i<U.size(); i++) d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i});
    ll length=ask(qs)/A;
    stack<int> q;
    q.push(0);
    vs[0]=1;
    while (!q.empty())
    {
        int u=q.top();
        q.pop();
        for (auto [v, idx]:d[u]) if (!vs[v]) res[t]=v, id[t++]=idx, vs[v]=1, q.push(v);
    }
    l=0, r=N-1;
    while (l<r)
    {
        int md=(l+r)/2;
        for (int i=0; i<N-1; i++) qs[i]=0;
        for (int i=0; i<=md; i++) qs[id[i]]=1;
        if (ask(qs)/B==length) r=md;
        else l=md+1;
    }
    int h=res[l];
    t=0;
    for (int i=0; i<N; i++) vs[i]=0;
    q.push(h);
    vs[h]=1;
    while (!q.empty())
    {
        int u=q.top();
        q.pop();
        for (auto [v, idx]:d[u]) if (!vs[v]) res[t]=v, id[t++]=idx, vs[v]=1, q.push(v);
    }
    l=0, r=N-1;
    while (l<r)
    {
        int md=(l+r)/2;
        for (int i=0; i<N-1; i++) qs[i]=0;
        for (int i=0; i<=md; i++) qs[id[i]]=1;
        if (ask(qs)/B==length) r=md;
        else l=md+1;
    }
    answer(h, res[l]);
}

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

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int i=0; i<U.size(); i++) d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i});
      |                   ~^~~~~~~~~

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