Submission #493556

#	Time	Username	Problem	Language	Result	Execution time	Memory
493556		nekotizimo	Race (IOI11_race)	C++17	43 / 100	314 ms	82500 KiB

race

#include "race.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;
typedef long long ll;
template<typename a, typename b> ostream& operator<< (std::ostream &out, const pair<a, b> &p) {
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}

const int MAXN = 2e5 + 5;
ll _K, ans = MAXN, o1[MAXN], o2[MAXN];
vector< pair<ll, ll> > adj_list[MAXN];
map<ll, ll> paths[MAXN]; // length, num

void dfs(int cur, int p) {
    for (auto n : adj_list[cur]) {
        ll neigh = n.first, l = n.second;
        if (p == neigh) continue;
        dfs(neigh, cur);
        if (paths[neigh].size() > paths[cur].size()) {
            paths[cur].swap(paths[neigh]);
            o1[neigh] += l;
            o2[neigh]++;
            o1[cur] -= l;
            o2[cur]--;
            swap(o1[cur], o1[neigh]);
            swap(o2[cur], o2[neigh]);
        }
        for (auto e : paths[neigh]) {
            if (paths[cur].count(_K - (e.first + l + o1[neigh]) - o1[cur])) {
                ans = min(ans, paths[cur][_K - (e.first + l + o1[neigh]) - o1[cur]] + e.second + 1 + o2[neigh] + o2[cur]); 
                //cerr << cur << ": " << paths[cur][_K - (e.first + l + o1[neigh]) - o1[cur]] + e.second + 1 + o2[neigh] + o2[cur] << endl;
                // only with newly added cuz from differnt subtrees
            }
            if (paths[cur].count(e.first + l + o1[neigh] - o1[cur])) {
                paths[cur][e.first + l + o1[neigh] - o1[cur]] = min(paths[cur][e.first + l + o1[neigh] - o1[cur]], e.second + 1 + o2[neigh] - o2[cur]);
            }
            else paths[cur][e.first + l + o1[neigh] - o1[cur]] = e.second + 1 + o2[neigh] - o2[cur];
        }
    }
    if (paths[cur].count(_K - o1[cur])) {
        ans = min(ans, paths[cur][_K - o1[cur]] + o2[cur]);
        //cerr << cur << ": " << paths[cur][_K - o1[cur]] + o2[cur] << endl;
    }

    paths[cur][-o1[cur]] = -o2[cur];
    
    //cerr << cur << ": " << o1[cur] << " " << o2[cur] << " ";
    // for (auto e : paths[cur]) //cerr << e << " ";
    //cerr << endl;
}

int best_path(int N, int K, int H[][2], int L[]) {
    _K = K;
    for (int i = 0; i < N - 1; i++) {
        adj_list[H[i][0]].push_back({H[i][1], L[i]}), adj_list[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(0, -1);
    return (ans == MAXN) ? -1 : ans;
}

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