Submission #594389

#	Time	Username	Problem	Language	Result	Execution time	Memory
594389		TimDee	Highway Tolls (IOI18_highway)	C++14	6 / 100	238 ms	12196 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);
}

int find_start(vector<vector<pair<int,int>>>&adj, int n, int b, int d) {
    vector<int> leaves;
    for (int i=0; i<n; ++i) {
        if (adj[i].size()==1) leaves.push_back(i);
    }
    vector<int> dist(n,0);
    vector<vector<int>> D(n);

    queue<int> q;
    vector<int> vis(n,0);
    for (auto u:leaves) { q.push(u); vis[u]=1; }
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (auto it:adj[u]) {
            int v=it.first;
            if (!vis[v]) {
                vis[v]=1;
                dist[v]=dist[u]+1;
                q.push(v);
            }
        }
    }
    for (int i=0; i<n; ++i) D[dist[i]].push_back(i);

    int l=0, r=n-1;
    vector<int> scuza(n-1,1), paiu;
    while (l<r) {
        paiu=scuza;
        int mid=(l+r)/2;
        for (int i=0; i<=mid; ++i) {
            for (auto u:D[i]) {
                for (auto it:adj[u]) {
                    paiu[it.second]=0;
                }
            }
        }
        int x=ask(paiu);
        if (x<b*d) r=mid;
        else l=mid+1;
    }
    vector<int> amogus; for (auto u:D[r]) amogus.push_back(u);
    l=0, r=amogus.size()-1;
    while (l<r) {
        int mid=(l+r+1)/2;
        paiu=scuza;
        for (int i=l; i<mid; ++i) {
            for (auto it:adj[amogus[i]]) {
                paiu[it.second]=0;
            }
        }
        int x=ask(paiu);
        if (x<d*b) r=mid-1;
        else l=mid;
    }
    return amogus[r];
}

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;}
    int s=find_start(adj,n,b,dist);

    queue<int> q;
    q.push(s);
    vector<int> d(n,0);
    vector<int> D;
    vector<int> vis(n,0); vis[s]=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(s,D[r]);
}

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