Submission #431498

#	Time	Username	Problem	Language	Result	Execution time	Memory
431498		arayi	Highway Tolls (IOI18_highway)	C++17	51 / 100	272 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ad push_back
#define MP make_pair
#define lli long long
#define fr first
#define sc second
const int N = 1e6 + 30;

int n, m;
vector<pair<int, int> > g[N], fp;
vector<int> w;
int xr[N], col[N];
pair<int, int> pr[N];
lli sum;
void dfs(int v, int par)
{
    for(auto p : g[v])
    {
        if(p.fr == par) continue;
        xr[p.fr] = xr[v] + 1;
        pr[p.fr] = MP(v, p.sc);
        dfs(p.fr, v);
    }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) 
{
    n = N, m = U.size();
    for (int i = 0; i < m; i++)
    {
        w.ad(0);
        g[U[i]].ad(MP(V[i], i));
        g[V[i]].ad(MP(U[i], i));
    }
    sum = ask(w);
    dfs(0, 0);
    for (int i = 1; i < n; i++) 
    {
        fp.ad(MP(xr[i], pr[i].sc));
        //cout << pr[i].sc << " ";
    }
    sort(fp.begin(), fp.end());
    reverse(fp.begin(), fp.end());
    int l = 0, r = m - 1, ans = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = 0; i < m; i++) w[i] = 0;
        for (int i = 0; i <= mid; i++) w[fp[i].sc] = 1;
        if(ask(w) == sum) l = mid + 1;
        else ans = mid, r = mid - 1;
    }
    if(xr[U[fp[ans].sc]] > xr[V[fp[ans].sc]]) ans = U[fp[ans].sc];
    else ans = V[fp[ans].sc];
    int S = ans;
    //cout << S << endl;
    for (int i = 0; i < m; i++) w[i] = 0;
    int v = ans;
    while(v)
    {
        w[pr[v].sc] = 1;
        v = pr[v].fr;
    }
    lli sm = ask(w);
    int s = (sm - sum) / (B - A);
    v = ans;
    for (int i = 0; i < s; i++)
    {
        col[pr[v].sc] = 1;
        v=pr[v].fr;
    }
    l = 0, r = m - 1, ans = -1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = 0; i < m; i++) w[i] = col[i];
        for (int i = 0; i <= mid; i++) w[fp[i].sc] = 1;
        if(ask(w) == sm) l = mid + 1;
        else ans = mid, r = mid - 1;
    }
    if(ans == -1) ans = v;
    else if(xr[U[fp[ans].sc]] > xr[V[fp[ans].sc]]) ans = U[fp[ans].sc];
    else ans = V[fp[ans].sc];
    int T = ans;
    answer(S, T);
}

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