제출 #680956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680956		nicky4321	경주 (Race) (IOI11_race)	C++14	0 / 100	13 ms	24916 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, int cnt){
    if(val > k)
        return;
    if(dis.count(k - val)){
        ans = min(ans, cnt + 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, cnt + 1);
	}
}
 
void calc2(int now, int from, int d, ll val, int cnt){
    if(val > k){
        return;
    }
    if(dis.count(val) != 0){
        dis[val] = min(dis[val], cnt);
    }else{
        dis[val] = cnt;
    }
	for(pii y : edge[now]){
        int i = y.F;
		if(vis[i] || i == from)
			continue;
		calc2(i, now, d + 1, val + y.S, cnt + 1);
	}
}
 
void solve(int x){
	dfs(x, x);
	half = cnt[x] / 2;
	int c = find(x, x);
	// cout << c << '\n';
	vis[c] = 1;
	dis[0] = 1;
	for(pii i : edge[c]){
        int y = i.F;
		if(!vis[y]){
			calc1(y, y, 1, 0, 1);
			calc2(y, y, 1, 0, 1);
		}
	}
    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[]){
    IOS
    n = N;
    k = K;
    for(int i = 0;i < n - 1;i++){
        edge[H[i][0]].PB(MK(H[i][1], i));
        edge[H[i][1]].PB(MK(H[i][0], i));
        w[i] = L[i];
    }
    solve(0);
    return ans;
}

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