Submission #403962

#	Time	Username	Problem	Language	Result	Execution time	Memory
403962		idk321	Highway Tolls (IOI18_highway)	C++11	51 / 100	450 ms	262148 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int n, m, a, b;
vector<int> u;
vector<int> v;

const int N = 90000;


int edges;
ll minCost;
vector<int> adj[N];
vector<int> adj2[N];




void addInSubtree(int node, int par, vector<int>& w)
{
    for (int i : adj2[node])
    {
         w[i] = 1;
    }

    for (int next : adj[node])
    {
        if (next == par) continue;
        addInSubtree(next, node, w);
    }
}

ll subtreeCost(int node, int par)
{
    vector<int> w(m);
    addInSubtree(node, par, w);
    return ask(w);
}

void addEnds(int node, int par, int needed, int ch, vector<int>& possEnds)
{
    if (ch == needed)
    {
        possEnds.push_back(node);
        return;
    }

    for (int next : adj[node])
    {
        if (next == par) continue;
        addEnds(next, node, needed, ch + 1, possEnds);
    }
}

int getIn(vector<int>& nodes)
{
    int from = 0;
    int to = nodes.size() - 1;
    int res = -1;
    vector<int> w(m);
    while (from <= to)
    {
        int mid = (from + to) / 2;
        w.clear();
        w.resize(m);
        for (int i = 0; i <= mid; i++)
        {
            for (int j : adj2[nodes[i]])
            {
                w[j] = 1;
            }
        }

        ll cur = ask(w);
        if (cur == minCost)
        {
            from = mid + 1;
        } else
        {
            res = nodes[mid];
            to = mid - 1;
        }
    }

    return res;
}

int getSubtreeEnd(int node, int par)
{
    ll cost = subtreeCost(node, par);
    int needed = (cost - minCost) / (b - a);
    vector<int> possEnds;
    addEnds(node, par, needed, 1, possEnds);

    int res = getIn(possEnds);
    return res;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n = N;
    a = A;
    b = B;
    u = U;
    v = V;
    m = v.size();

    for (int i = 0; i < m; i++)
    {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
        adj2[u[i]].push_back(i);
        adj2[v[i]].push_back(i);
    }

    vector<int> w(m);
    minCost = ask(w);
    edges = minCost / a;

    int from = 0;
    int to = n - 2;
    int res = -1;
    while (from <= to)
    {
        int mid = (from + to) / 2;
        w.clear();
        w.resize(m);
        for (int i = 0; i <= mid; i++)
        {
            w[i] = true;
        }

        ll cur = ask(w);
        if (cur == minCost)
        {
            from = mid + 1;
        } else
        {
            res = mid;
            to = mid - 1;
        }
    }

    int x = u[res];
    int y = v[res];
    int rx = getSubtreeEnd(x, y);
    int ry = getSubtreeEnd(y, x);
    answer(rx, ry);
}


/*
15 14 1 2 0 3
0 4
4 5
4 3
12 3
3 7
7 8
8 11
8 10
6 13
6 14
6 9
3 6
2 3
10 1
*/

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