Submission #594346

#	Time	Username	Problem	Language	Result	Execution time	Memory
594346		TimDee	Highway Tolls (IOI18_highway)	C++14	18 / 100	141 ms	8760 KiB

highway

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

void _7pts(int n, int b, int d) {
    int l=0, r=n-2;
    vector<int> scuza(n-1,1), paiu;
    while (l<r) {
        paiu = scuza;
        int mid=(l+r)/2;
        for (int i=l; i<=mid; ++i) paiu[i]=0;
        int x=ask(paiu);
        if (x<b*d) r=mid;
        else l=mid+1;
    }
    //cout<<r<<' '<<r+d<<'\n';
    answer(r,r+d);
}

void find_pair(int n, vector<int>u, vector<int> v, int a, int b) {
    int m=u.size();
    vector<int> paiu(m,1);
    int dist=ask(paiu)/b;
    vector<vector<pair<int,int>>> adj(n);
    for (int i=0; i<m; ++i) {
        adj[u[i]].push_back({v[i],i});
        adj[v[i]].push_back({u[i],i});
    }

    int foo=1; for (int i=0; i<m; ++i) foo&=(u[i]+1==v[i]);
    if (foo) {
        _7pts(n,b,dist);
        return;
    }

    queue<int> q;
    q.push(0);
    vector<int> d(n,0);
    vector<int> D;
    vector<int> vis(n,0); vis[0]=1;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (auto it:adj[u]) {
            int v=it.first;
            if (!vis[v]) {
                d[v]=d[u]+1;
                q.push(v);
                vis[v]=1;
            }
        }
    }
    for (int i=0; i<n; ++i) {
        if (d[i]==dist) D.push_back(i);
    }
    int l=0, r=D.size()-1;
    vector<int> scuza(m,1);
    while (l<r) {
        int mid=(l+r+1)/2;
        paiu=scuza;
        for (int i=l; i<mid; ++i) {
            for (auto it:adj[D[i]]) {
                paiu[it.second]=0;
            }
        }
        int x=ask(paiu);
        if (x<dist*b) r=mid-1;
        else l=mid;
    }
    answer(0,D[r]);
}

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