Submission #317347

#	Time	Username	Problem	Language	Result	Execution time	Memory
317347		neki	Race (IOI11_race)	C++14	0 / 100	10 ms	14464 KiB

race

#include <bits/stdc++.h>
//#include "race.h"
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 200100
#define pa pair<ll, ll>
#define ld long double 

ll ans=llmax, n, k, mod[mn], h[mn];
map<ll, ll> st[mn];
vc<pa> edg[mn];
void dfs(ll u, ll p){
    if(p!=-1 and edg[u].size()==1){st[u][0]=0;return;}
    ll ch=-1;
    fore(v, edg[u])if(v.fi!=p){
        h[v.fi]=h[u]+1;
        dfs(v.fi, u);
        mod[v.fi]+=v.se;
        if(ch==-1 or st[v.fi].size() > st[ch].size()) ch=v.fi;
    }
    swap(st[ch], st[u]);swap(mod[u], mod[ch]);
    fore(v, edg[u]) if(v.fi!=p and v.fi!=ch){
        fore(pot, st[v.fi]){
            if((k-pot.fi-mod[v.fi])>0 and st[u].find((k-pot.fi-mod[v.fi])-mod[u])!=st[u].end()) ans=min(ans, pot.se+st[u][(k-pot.fi-mod[v.fi])-mod[u]]-2 * h[u]);
            if((k-pot.fi-mod[v.fi])==0) ans=min(ans, h[v.fi]-h[u]);
        }
        fore(pot, st[v.fi]){ 
            if(st[u].find(pot.fi+mod[v.fi]-mod[u])==st[u].end()) st[u][pot.fi+mod[v.fi]-mod[u]]=llmax;
            st[u][pot.fi+mod[v.fi]-mod[u]]=min(st[u][pot.fi+mod[v.fi]-mod[u]], pot.se);
        }
    }
}
ll best_path(int N,int  K, int h[][2], int l[]){
    n=N, k=K;
    loop(i, 0, n-1){
        edg[h[i][0]].ps(make_pair(h[i][1], l[i]));
        edg[h[i][1]].ps(make_pair(h[i][0], l[i]));
    }
    dfs(0, -1);
    return (ans>n+3)? -1:ans;
}

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