Submission #296105

#	Time	Username	Problem	Language	Result	Execution time	Memory
296105		Autoratch	Highway Tolls (IOI18_highway)	C++14	12 / 100	294 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 9e4 + 1;

int n,m,a,b;
vector<int> adj[N],ass;
vector<pair<int,int> > res;
vector<tuple<int,int,int> > ed;
int lv[N];

long long ash(vector<int> x)
{
    ass.assign(m,0);
    for(int y : x) ass[y] = 1;
    return ask(ass);
}

void dfs(int u,int p)
{
    lv[u] = lv[p]+1;
    for(int v : adj[u]) if(v!=p) dfs(v,u);
}

void find_pair(int N, vector<int> U, vector<int> V, int A,int B) 
{
    n = N,m = U.size();
    a = A,b = B;
    for(int i = 0;i < m;i++)
    {
        int a = U[i],b = V[i];
        a++,b++;
        adj[a].push_back(b);
        adj[b].push_back(a);
        ed.push_back({i,a,b});
        ed.push_back({i,b,a});
    }
    vector<int> tmp;
    long long dist = ash(tmp)/a;
    dfs(1,0);
    for(auto [id,x,y] : ed) if(lv[x]==dist+1 and lv[y]<lv[x])
    {
        res.push_back({id,x});
    }
    int l = 0,r = res.size();
    r--;
    while(l<r)
    {
        int m = (l+r)/2;
        tmp.clear();
        for(int i = l;i <= m;i++) tmp.push_back(res[i].first);
        long long ret = ash(tmp);
        if(ret==dist*a) l = m+1;
        else r = m;
    }
    answer(0,res[l].second-1);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [id,x,y] : ed) if(lv[x]==dist+1 and lv[y]<lv[x])
      |              ^

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