Submission #499070

#	Time	Username	Problem	Language	Result	Execution time	Memory
499070		blue	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	53 ms	10428 KiB

roadsideadverts

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;

const int mx = 50'000;
const int lg = 15;

int N;
int Q;

vector<pii> edge[mx];

vi dist0(mx, 0);
vi par(mx, 0);
vi depth(mx, 0);

int anc[mx][1+lg];

int ct = -1;
vi dfs_ind(mx, -1);



void dfs(int u)
{
    dfs_ind[u] = ++ct;
    for(auto e: edge[u])
    {
        int v = e.first;
        int w = e.second;

        if(v == par[u]) continue;

        depth[v] = depth[u] + 1;
        par[v] = u;
        dist0[v] = dist0[u] + w;

        dfs(v);
    }
}

int getanc(int u, int d)
{
    for(int e = lg; e >= 0; e--)
        if(d & (1 << e))
            u = anc[u][e];

    return u;
}

int lca(int u, int v)
{
    if(depth[v] < depth[u]) swap(u, v);

    for(int e = lg; e >= 0; e--)
        if((depth[v] - depth[u]) & (1 << e))
            v = anc[v][e];

    if(u == v) return u;

    for(int e = lg; e >= 0; e--)
    {
        if(anc[u][e] == anc[v][e]) continue;
        u = anc[u][e];
        v = anc[v][e];
    }

    return anc[u][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int e = 0; e < N-1; e++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }

    par[0] = 0;
    dfs(0);


    for(int i = 0; i < N; i++) anc[i][0] = par[i];
    for(int e = 1; e <= lg; e++)
        for(int i = 0; i < N; i++)
            anc[i][e] = anc[ anc[i][e-1] ][e-1];

    int Q;
    cin >> Q;

    for(int j = 0; j < Q; j++)
    {
        vi q(5);
        for(int f = 0; f < 5; f++) cin >> q[f];

        sort(q.begin(), q.end(), [] (int u, int v)
        {
            return (dfs_ind[u] < dfs_ind[v]);
        });

        for(int f = 0; f+1 < 5; f++)
        {
            q.push_back(lca(q[f], q[f+1]));
        }

        sort(q.begin(), q.end(), [] (int u, int v)
        {
            return (dfs_ind[u] < dfs_ind[v]);
        });

        vi st;
        st.push_back(q[0]);

        int ans = 0;

        for(int u: q)
        {
            while(getanc(u, depth[u] - depth[st.back()]) != st.back())
                st.pop_back();

            ans += dist0[u] - dist0[st.back()];

            st.push_back(u);
        }

        cout << ans << '\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30