제출 #1268240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268240		wedka	경주 (Race) (IOI11_race)	C++20	0 / 100	7 ms	14408 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxN = 2e5+5;
ll INF = 1e12;
ll sum[maxN];
ll depth[maxN];
vector<vector<pair<ll,ll>>> adj(maxN);
vector<map<ll,ll>> mp(maxN);
ll k,n;
ll ans = INF;

void dfs1(int s, int p) {
    depth[s] = depth[p]+1;
    for(auto [w,u] : adj[s]) {
        if(u == p) continue;
        sum[u] = sum[s]+w;
        dfs1(u,s);
    }
}

void dfs(int s, int p) {
    if(sum[s] <= 3e6) {
        if(mp[s][sum[s]] == 0) mp[s][sum[s]] = depth[s];
        else mp[s][sum[s]] = min(mp[s][sum[s]], depth[s]);
    }
    for(auto ps : adj[s]) {
        int w = ps.first, u = ps.second;
        if(u == p) continue;
        dfs(u,s);
        if(mp[u].size() > mp[s].size()) swap(mp[u],mp[s]);
        for(auto pr : mp[u]) {
            int cur = mp[s][k-pr.first + 2*sum[s]];
            if(cur != 0) {
                ans = min(ans,cur+pr.second - 2*depth[s]);
            }
        }
        for(auto pr : mp[u]) {
            mp[s].insert(pr);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for(int i = 0; i < N-1; i++) {
        int a = H[i][0],b = H[i][1], w = L[i];
        adj[a].push_back({w,b});
        adj[b].push_back({w,a});
    }
    sum[0] = 0;
    depth[0] = 1;
    dfs1(0,0);
    dfs(0,0);
    if(ans == INF) return -1;
    return ans;
}

/*int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

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