제출 #713418

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

race

#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
vector<pair<int, int> > adj[N];
map<long long, long long> mp[N];
long long distToRoot[N];
long long weightPathToRoot[N];
int n, k;
long long ans;
void dfs(int u, int p, long long currentsum, int height) {
	mp[u][currentsum] = height;
	weightPathToRoot[u] = currentsum;
	distToRoot[u] = height;
	for (pair<int, int> x : adj[u]) {
        int v = x.first;
        if(v != p){
            dfs(v, u, currentsum + x.second, height + 1);
        }
	}
}
void dfs2(int u, int p) {
	long long target = k + 2 * weightPathToRoot[u];
	for (pair<int, int> x : adj[u]) {
        int v = x.first;
        if(v != p){
            dfs2(v, u);
            if (mp[v].size() > mp[u].size()){
                swap(mp[v], mp[u]);
            }
            for (auto i : mp[v]) {
                if (mp[u].find(target - i.first) != mp[u].end()) {
                    ans = min(ans, mp[u][target - i.first] + i.second - 2 * distToRoot[u]);
                }
            }
            for (auto i : mp[v]) {
                if (mp[u].find(i.first) == mp[u].end()) {
                    mp[u].insert(i);
                } else {
                    mp[u][i.first] = min(mp[u][i.first], i.second);
                }
            }
        }
	}
}
int best_path(int n_, int k_, int edges[][2], int weights[]) {
	if (k_ == 1){
        return 0;
    }
	n = n_;
	k = k_;
	ans = 1e18;
	for (int i = 0; i < n - 1; i++) {
		int u = edges[i][0];
		int v = edges[i][1];
		adj[u].push_back(make_pair(v, weights[i]));
		adj[v].push_back(make_pair(u, weights[i]));
	}
	dfs(0, -1, 0, 0);
	dfs2(0, -1);
	return ans == 1e18 ? -1 : ans;
}

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