Submission #34569

#	Time	Username	Problem	Language	Result	Execution time	Memory
34569		top34051	Race (IOI11_race)	C++14	100 / 100	897 ms	58620 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 200005;
const int inf = 1e6;

int n,k,ans;
int cur, h[maxn], sz[maxn], st[maxn], ft[maxn], p[maxn];
long long sum[maxn];
vector<int> go[maxn];
vector<pii> edge[maxn];
map<long long,int> s;

void dfs(int u,int last) {
    st[u] = ++cur; p[cur] = u;
    sz[u] = 1; h[u] = h[last]+1;
    for(auto t : edge[u]) {
        int v = t.X, val = t.Y;
        if(v!=last) {
            sum[v] = sum[u] + val;
            dfs(v,u);
            sz[u] += sz[v];
        }
    }
    ft[u] = cur;
//    printf("%d : [%d, %d]   h = %d   sz = %d   sum = %lld\n",u,st[u],ft[u],h[u],sz[u],sum[u]);
}

void add(long long x,int val) {
    if(s.find(x)==s.end()) s[x] = val;
    else s[x] = min(s[x],val);
}

int get(long long x) {
    if(s.find(x)==s.end()) return inf;
    return s[x];
}

void solve(int u,int last,int keep) {
    int mx = 0, big = -1;
    for(auto v : go[u]) if(v!=last && sz[v]>mx) mx = sz[v], big = v;
    for(auto v : go[u]) if(v!=last && v!=big) solve(v,u,0);
    if(big!=-1) solve(big,u,1);
    //solve
//    printf("solve %d\n",u);
    add(sum[u],h[u]);
    ans = min(ans,get(k+sum[u])-h[u]);
    for(auto v : go[u]) {
        if(v!=last && v!=big) {
            for(int i=st[v];i<=ft[v];i++) {
//                printf("\ttry %d : (%lld) : want %lld\n",p[i],sum[p[i]],k-sum[p[i]]+2*sum[u]);
                ans = min(ans,get(k-sum[p[i]]+2*sum[u])+h[p[i]]-2*h[u]);
            }
            for(int i=st[v];i<=ft[v];i++) add(sum[p[i]],h[p[i]]);
        }
    }
    //delete
    if(!keep) s.clear();
}

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 x = H[i][0]+1, y = H[i][1]+1, val = L[i];
        edge[x].push_back({y,val}); edge[y].push_back({x,val});
        go[x].push_back(y); go[y].push_back(x);
    }
    dfs(1,0);
    ans = inf;
    solve(1,0,0);
    if(ans>n) return -1;
    return ans;
}

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