제출 #680961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680961		nicky4321	경주 (Race) (IOI11_race)	C++14	100 / 100	988 ms	62020 KiB

race

#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <array>
#include <cassert>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MK make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
vector<pii> edge[MAX];
int cnt[MAX], vis[MAX], w[MAX];
int n, k, half;
int ans = 2e9;
map<ll, int> dis;
 
void dfs(int now, int from){
	cnt[now] = 1;
	for(pii y : edge[now]){
        int i = y.F;
		if(i == from || vis[i])
			continue;
		dfs(i, now);
		cnt[now] += cnt[i];
	}
}
 
int find(int now, int from){
	for(pii y : edge[now]){
        int i = y.F;
		if(i == from || vis[i])
			continue;
		if(cnt[i] > half)
			return find(i, now);
	}
	return now;
}
 
void calc1(int now, int from, int d, ll val){
    if(val > k)
        return;
    if(dis.count(k - val)){
        ans = min(ans, d + dis[k - val]);
    }
	for(pii y: edge[now]){
        int i = y.F;
		if(vis[i] || i == from)
			continue;
		calc1(i, now, d + 1, val + y.S);
	}
}
 
void calc2(int now, int from, int d, ll val){
    if(val > k){
        return;
    }
    if(dis.count(val) != 0){
        dis[val] = min(dis[val], d);
    }else{
        dis[val] = d;
    }
	for(pii y : edge[now]){
        int i = y.F;
		if(vis[i] || i == from)
			continue;
		calc2(i, now, d + 1, val + y.S);
	}
}
 
void solve(int x){
	dfs(x, x);
	half = cnt[x] / 2;
	int c = find(x, x);
	vis[c] = 1;
	dis[0] = 0;
	for(pii i : edge[c]){
        int y = i.F;
		if(!vis[y]){
			calc1(y, y, 1, i.S);
			calc2(y, y, 1, i.S);
		}
	}
    dis.clear();
	for(pii i : edge[c]){
		if(!vis[i.F])
			solve(i.F);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N;
    k = K;
    for(int i = 0;i < n - 1;i++){
        edge[H[i][0]].PB(MK(H[i][1], L[i]));
        edge[H[i][1]].PB(MK(H[i][0], L[i]));
    }
    solve(0);
    return (ans == 2e9 ? -1 : ans);
}

// int main(){
//     IOS
//     int N, K;
//     cin >> N >> K;
//     int H[N - 1][2], L[N - 1];
//     for(int i = 0;i < N - 1;i++){
//         cin >> H[i][0] >> H[i][1];
//     }
//     for(int i = 0;i < N - 1;i++)
//         cin >> L[i];
//     cout << best_path(N, K, H, L) << '\n';
//     return 0;
// }

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