제출 #748591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748591		ZeroCool	Race (IOI11_race)	C++17	100 / 100	397 ms	108108 KiB

race

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


const int mxn = 200005;
const int inf = 1e9;

using namespace std;
set<pair<ll,int> > s[mxn];
vector<pair<int,int> > g[mxn];

int n,k;

int ans;

void dfs(int x,int p,ll dis,int dep){
	s[x].insert({dis,dep});
	for(auto par : g[x]){
		int y = par.first;
		int z = par.second;
		if(y == p)continue;

		dfs(y,x,dis+z,dep+1);

		if(s[x].size() < s[y].size())swap(s[x],s[y]);

		for(auto par2 : s[y]){
			int len= par2.first;
			int cnt = par2.second;

			ll q = k - len + 2*dis;

			auto it = s[x].lower_bound({q,0});

			if(it != s[x].end() && (*it).first == q){
				ans = min(ans, (*it).second + cnt - 2 * dep);
			}
		}
		s[x].insert(s[y].begin(),s[y].end());
	}
}


int best_path(int _n, int _k, int H[][2], int L[]){
	n = _n;
	k = _k;
	//vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n - 1; i++) {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    ans = n;

    //vector<set<pair<ll, int>>> s(n);

    // auto dfs = [&](auto dfs, int x, int p, ll dis, int dep) -> void {
    //     //s[x].emplace(dis, dep);
	// 	s[x].insert({dis,dep});
    //     for (auto [y,z] : g[x]) {
	// 		if (y == p) continue;
            
    //         dfs(dfs, y, x, dis + z, dep + 1);

    //         if (s[x].size() < s[y].size()) {
    //             swap(s[x], s[y]);
    //         }

    //         for (auto [len, cnt] : s[y]) {
    //             ll q = k - len + 2 * dis;
    //             auto it = s[x].lower_bound({q, 0});
    //             if (it != s[x].end() && (*it).first == q) {
    //                 ans = min(ans, (*it).second + cnt - 2 * dep);
    //             }
    //         }
    //         s[x].insert(s[y].begin(), s[y].end());
    //     }
    // };
    dfs( 0, -1, 0, 0);
    if (ans == n) {
        ans = -1;
    }
    return ans;

}	
//Pls work

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