Submission #601815

#	Time	Username	Problem	Language	Result	Execution time	Memory
601815		Hanksburger	통행료 (IOI18_highway)	C++17	18 / 100	163 ms	21388 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> distu[90005], distv[90005], vec;
vector<pair<int, int> > adj[90005];
pair<int, int> par[90005];
void dfs(int u, int p, int d, bool b)
{
    if (b)
        distu[d].push_back(u);
    else
        distv[d].push_back(u);
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second;
        if (v!=p)
        {
            par[v]={u, w};
            dfs(v, u, d+1, b);
        }
    }
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
    for (int i=0; i<=n-2; i++)
        vec.push_back(0);
    long long res=ask(vec)/a;
    int l=0, r=n-2, d, ans;
    while (l<r)
    {
        int mid=(l+r)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=l; i<=mid; i++)
            vec[i]=1;
        if (ask(vec)==res*a)
            l=mid+1;
        else
            r=mid;
    }
    for (int i=0; i<=n-2; i++)
    {
        if (i!=l)
        {
            adj[u[i]].push_back({v[i], i});
            adj[v[i]].push_back({u[i], i});
        }
    }
    dfs(u[l], -1, 0, 1);
    dfs(v[l], -1, 0, 0);
    l=0, r=n-2;
    while (l<r)
    {
        int mid=(l+r+1)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=mid; i<=r; i++)
            for (int j:distu[i])
                vec[par[j].second]=1;
        if (ask(vec)==res*a)
            r=mid-1;
        else
            l=mid;
    }
    d=l;
    l=0, r=distu[d].size()-1;
    while (l<r)
    {
        int mid=(l+r)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=l; i<=mid; i++)
            vec[par[distu[d][i]].second]=1;
        if (ask(vec)==res*a)
            l=mid+1;
        else
            r=mid;
    }
    ans=distu[d][l];
    d=res-d-1;
    l=0, r=distv[d].size()-1;
    while (l<r)
    {
        int mid=(l+r)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=l; i<=mid; i++)
            vec[par[distv[d][i]].second]=1;
        if (ask(vec)==res*a)
            l=mid+1;
        else
            r=mid;
    }
    answer(ans, distv[d][l]);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int, int, bool)':
highway.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

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