Submission #1098544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098544		SulA	Race (IOI11_race)	C++17	0 / 100	7 ms	14424 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;

map<long long, int> stl[200'000];
vector<pair<int,int>> adj[200'000];
int dep[200'000], ans = 1e9;
long long dist[200'000], k;

void init(int u = 0, int p = 0) {
    stl[u][dist[u]] = dep[u];
    for (auto [v, w] : adj[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + w;
        init(v, u);
    }
}

void dfs(int u = 0, int p = 0) {
    long long target = k + 2*dist[u];
    for (auto [v, w] : adj[u]) if (v != p) {
        dfs(v, u);

        if (stl[v].size() > stl[u].size()) swap(stl[u], stl[v]);
        for (auto [len, edges] : stl[v]) {
            if (stl[u].count(target - len)) {
                cout << u << " " << v << "\n";
                cout << len << " " << target - len << '\n';
                ans = min(ans, stl[u][target - len] + edges - 2*dep[u]);
            }
        }
        for (auto [len, edges] : stl[v]) {
            if (stl[u].count(len)) {
                stl[u][len] = min(stl[u][len], edges);
            } else {
                stl[u][len] = edges;
            }
        }
    }
//    cout << u << ":\n";
//    for (auto [len, edges] : stl[u]) cout << len << " " << edges << "\n";
//    cout << '\n';
}

int best_path(int n, int _k, int h[][2], int l[]) {
    k = _k;
    for (int i = 0; i < n-1; i++) {
        adj[h[i][0]].emplace_back(h[i][1], l[i]);
        adj[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    init();
    dfs();
    return ans == 1e9 ? -1 : ans;
}

//signed main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);
//
//    cout << best_path(
//            4,
//            3,
//            {
//                    {0, 1},
//                    {1, 2},
//                    {1, 3}
//            },
//            {
//                    1,
//                    2,
//                    4
//            }
//            );
//}

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