Submission #552876

#	Time	Username	Problem	Language	Result	Execution time	Memory
552876		DrearyJoke	Race (IOI11_race)	C++17	21 / 100	3075 ms	46156 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio                                                                 \
    ios_base::sync_with_stdio(false);                                          \
    cin.tie(NULL);                                                             \
    cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int best_path(int n, int k, int H[][2], int L[]) {
    vector<vector<pii>> adj(n);

    for (int i = 0; i < n - 1; ++i) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    int ans = INT_MAX;
    function<gp_hash_table<ll, int, custom_hash>(int, int, int, ll)> dfs = [&](int v, int p, int d, ll l) -> gp_hash_table<ll, int, custom_hash> {
        gp_hash_table<ll, int, custom_hash> mp;
        mp[l] = d;
        for (auto u : adj[v]) {
            if (u.ff != p) {
                auto ret = dfs(u.ff, v, d + 1, l + u.ss);
                // cout << "RET: " << v << " " << u.ff << END;
                // for (auto u: ret) cout << u.ff << " " << u.ss << END;
                // cout << END;
                if (mp.size() < ret.size()) swap(mp, ret);
                for (auto x : ret) {
                    if (mp.find(k - x.ff + l * 2) != mp.end()) {
                        int pp = mp[k - x.ff + l * 2];
                        // cout << "In " << v << ": " << u.ff << " " << x.ff << " " << x.ss << " " << k - x.ff + l * 2 << " " << pp << " " << d << " " << l << END;
                        ans = min(ans, pp + x.ss - 2 * d);
                    }
                }
                for (auto x : ret) {
                    // k = a + b - v * 2
                    // cout << "In " << v << ": " << u.ff << " " << x.ff << " " << x.ss << END;
                    // if (mp.find(k - x.ff + l * 2) != mp.end()) {
                    //     int pp = mp[k - x.ff + l * 2];
                    //     cout << "In " << v << ": " << u.ff << " " << x.ff << " " << x.ss << " " << k - x.ff + l * 2 << " " << pp << " " << d << " " << l << END;
                    //     ans = min(ans, pp + x.ss - 2 * d);
                    // }
                    if (mp.find(x.ff) == mp.end())
                        mp[x.ff] = x.ss;
                    else
                        mp[x.ff] = min(mp[x.ff], x.ss);
                }
            }
        }
        return mp;
    };
    dfs(0, -1, 0, 0);
    return ans == INT_MAX ? -1 : ans;
    // return n;
}

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