Submission #1061778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061778		mnasser02	Race (IOI11_race)	C++17	100 / 100	307 ms	87360 KiB

race

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LSOne(S) ((S) & -(S))

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

int best_path(int n, int K, int edges[][2], int weights[]) {
    vector<vii> AL(n);
    for (int i = 0; i < n - 1; i++) {
        auto [u, v] = edges[i];
        int w = weights[i];
        AL[u].push_back({v, w});
        AL[v].push_back({u, w});
    }

    int ans = 1e9;
    auto dfs = [&](auto self, int u, int p, int d, ll s) -> map<ll, int> {
        map<ll, int> res;
        res[s] = d;
        ll targ = K + 2 * s;
        for (auto [v, w] : AL[u]) {
            if (v == p) continue;
            auto cur = self(self, v, u, d + 1, s + w);
            if (res.size() < cur.size()) swap(res, cur);
            for (auto [k, v] : cur) {
                if (res.count(targ - k)) ckmin(ans, v + res[targ - k] - 2 * d);
            }
            for (auto [k, v] : cur) {
                if (res.count(k))
                    ckmin(res[k], v);
                else
                    res[k] = v;
            }
        }
        return res;
    };
    dfs(dfs, 0, -1, 0, 0);
    return ans == 1e9 ? -1 : ans;
}
// int main() {
//     ios_base::sync_with_stdio(0), cin.tie(0);

//     int tc = 1;
//     // cin >> tc;

//     while (tc--) {
//         solve();
//     }
//     return 0;
// }

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