제출 #493580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493580		nekotizimo	경주 (Race) (IOI11_race)	C++17	100 / 100	398 ms	80872 KiB

race

#include "race.h"
#include <vector>
#include <map>
#include <iostream>
// #define IS_DEBUG
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 bool DEBUG = false;
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]); 
                
                if (DEBUG) 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
            }
        }
        for (auto e : paths[neigh]) {
            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];
            }
        }
        paths[neigh].clear();
    }
    if (paths[cur].count(_K - o1[cur])) {
        ans = min(ans, paths[cur][_K - o1[cur]] + o2[cur]);
        if (DEBUG) cerr << cur << ": " << paths[cur][_K - o1[cur]] + o2[cur] << endl;
    } 

    paths[cur][-o1[cur]] = -o2[cur];
    
    if (DEBUG) {
        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;
}

#ifdef IS_DEBUG
int main() {
    int n, k;
	cin >> n >> k;
    int h[MAXN][2], l[MAXN];
    for (int i = 0 ; i < n - 1; i++) {
        cin >> h[i][0] >> h[i][1] >> l[i];
    }

    cout << best_path(n, k, h, l) << endl;

	return 0;
}
#endif

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