Submission #1228245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228245		Good	Race (IOI11_race)	C++20	9 / 100	121 ms	25736 KiB

race

#include "bits/stdc++.h"
#include "race.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;

#define endl '\n'
#define pb push_back
#define eb emplace_back
// #define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define rev(i, a, b) for (int i = (a); i >= (b); --i)

const ll inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;

void my_assert(int e) {if (!e) abort();}

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

ll power(ll a, ll b, ll m = mod) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl;
#else
#define debug(x)
#endif



void calcsz(int nd, int p, int weight, vector<vector<pii>> &adj, vector<int> &sz, vector<int> &lvl, vector<ll> &pref, vector<int> &nodes, vector<pii> &sf) {
    lvl[nd] = lvl[p] + 1;
    sz[nd] = 1;
    pref[nd] = pref[p] + weight;
    sf[nd].ff = nodes.size();
    nodes.pb(nd);
    for (pii &v: adj[nd]) {
        if (v.ff != p) {
            calcsz(v.ff, nd, v.ss, adj, sz, lvl, pref, nodes, sf);
            sz[nd] += sz[v.ff];
        }
    }
    sf[nd].ss = nodes.size();
}

void dfs(int k, int nd, int p, vector<vector<pii>> &adj, vector<int> &sz, vector<int> &lvl, vector<ll> &pref, vector<int> &nodes, vector<pii> &sf, vector<map<ll, int>*> &mp, int &ans) {
    int big_child = -1, mxsz = 0;
    for (pii &v: adj[nd]) {
        if (v.ff != p) {
            dfs(k, v.ff, nd, adj, sz, lvl, pref, nodes, sf, mp, ans);
            if (mxsz < sz[v.ff]) big_child = v.ff, mxsz = sz[v.ff];
        }
    }

    if (big_child != -1) {
        mp[nd] = mp[big_child];
    } else {
        mp[nd] = new map<ll, int>();
    }

    for (pii &v: adj[nd]) {
        if (v.ff != p && v.ff != big_child) {
            map<ll, int> temp;
            for (int i = sf[v.ff].ff; i < sf[v.ff].ss; i++) {
                if (mp[nd]->find(0ll+k + 2*pref[nd] - pref[i]) != mp[nd]->end()) {
                    ans = min(ans, lvl[i] + (*mp[nd])[0ll+k + 2 * pref[nd] - pref[i]] - 2 * lvl[nd]);
                }

                if (temp.find(pref[i]) != temp.end()) temp[pref[i]] = min(temp[pref[i]], lvl[i]);               
                else temp[pref[i]] = lvl[i];
            }

            for (auto &j: temp) {
                if (mp[nd]->find(j.ff) != mp[nd]->end()) (*mp[nd])[j.ff] = min((*mp[nd])[j.ff], j.ss);
                else (*mp[nd])[j.ff] = j.ss;
            }
        }
    }

    if (mp[nd]->find(0ll+k + pref[nd]) != mp[nd]->end())
        ans = min(ans, (*mp[nd])[0ll+k + pref[nd]] - lvl[nd]);
    
    if (mp[nd]->find(pref[nd]) != mp[nd]->end()) (*mp[nd])[pref[nd]] = min((*mp[nd])[pref[nd]], lvl[nd]);
    else (*mp[nd])[pref[nd]] = lvl[nd];


    // cout << nd << '\n';
    // for (auto &j: (*mp[nd])) {
    //     cout << j.ff << ' ' << j.ss << '\n';
    // }
}

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pii>> adj(N);
    for (int i = 0; i < N; i++) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }

    vector<int> sz(N), lvl(N), nodes;
    vector<pii> sf(N);
    vector<ll> pref(N);
    vector<map<ll, int>*> mp(N);
    int ans = mod;
    calcsz(0, 0, 0, adj, sz, lvl, pref, nodes, sf);
    dfs(K, 0, 0, adj, sz, lvl, pref, nodes, sf, mp, ans);

    if (ans == mod) return -1;
    return ans;
}

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