Submission #716650

#	Time	Username	Problem	Language	Result	Execution time	Memory
716650		sheldon	Race (IOI11_race)	C++14	0 / 100	3 ms	4948 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int nax = 2e5 + 5;

vector<pair<int, int>> edges[nax];
int sz[nax];
bool dead[nax];

int cent (int u, int p, int comp) {
    for (auto v : edges[u]) {
        if (p != v.first && !dead[v.first] && sz[v.first] * 2 > comp) {
            return cent (v.first, u, comp);
        }
    }
    return u;
}

void dfs (int u, int p) {
    sz[u] = 1;
    for (auto v : edges[u]) {
        if (v.first != p && !dead[v.first]) {
            dfs (v.first, u);
            sz[u] += sz[v.first];
        }
    }
}
map<long long, int> mp;

void dfs2 (int u, int p, long long x, int depth) {
    if (mp[x] == 0 && x != 0) {
        mp[x] = depth;
    }
    mp[x] = min(mp[x], depth);
    for (auto v : edges[u]) {
        if (v.first != p && !dead[v.first]) {
            dfs2 (v.first, u, x + v.second, depth + 1);
        }
    }
}
int ans = 1e9;
int K;
void dfs3 (int u, int p, long long x, int depth) {
    if ((K - x > 0 && mp[K - x] > 0) || (K - x == 0))
        ans = min(ans, depth + mp[K - x]);
    cout << mp[K - x] << ' ' << x << '\n';
    for (auto v : edges[u]) {
        if (v.first != p && !dead[v.first]) {
            dfs3 (v.first, u, x + v.second, depth + 1);
        }
    }
}   

void decomp (int u) {
    dfs (u, - 1);
    int C = cent(u, -1, sz[u]);
    for (auto v : edges[C]) {
        if (!dead[v.first]) {
            dfs3(v.first, C, v.second, 1);
            dfs2 (v.first, C, v.second, 1);
        }
    }
    dead[C] = 1;
    mp.clear();
    for (auto v : edges[C]) {
        if (!dead[v.first])
            decomp (v.first);
    }
}

int best_path(int n, int k, int H[][2], int l[]) {
    K = k;
    for (int i = 0; i < n - 1; ++i) {
        int u = H[i][0];
        int v = H[i][1];
        int x = l[i];
        ++u, ++v;
        edges[u].push_back({v, x});
        edges[v].push_back({u, x});
    }
    decomp (1);
    return (ans == 1e9 ? -1 : ans);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57