Submission #601575

#	Time	Username	Problem	Language	Result	Execution time	Memory
601575		Hanksburger	Highway Tolls (IOI18_highway)	C++17	12 / 100	196 ms	27640 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[90005];
vector<int> dist[90005], vec;
pair<int, int> par[90005];
void dfs(int u, int p, int d)
{
    dist[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);
        }
    }
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
    int m=u.size();
    for (int i=0; i<m; i++)
    {
        adj[u[i]].push_back({v[i], i});
        adj[v[i]].push_back({u[i], i});
    }
    dfs(0, 0, 0);
    for (int i=0; i<m; i++)
        vec.push_back(0);
    long long res=ask(vec)/a;
    int l=0, r=dist[res].size()-1;
    while (l<r)
    {
        int mid=(l+r)/2;
        for (int i=0; i<m; i++)
            vec[i]=0;
        for (int i=l; i<=mid; i++)
            vec[par[dist[res][i]].second]=1;
        if (ask(vec)==res*a)
            l=mid+1;
        else
            r=mid;
    }
    answer(0, dist[res][l]);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int, int)':
highway.cpp:10: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]
   10 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

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