Submission #759180

#	Time	Username	Problem	Language	Result	Execution time	Memory
759180		Fidisk	Race (IOI11_race)	C++14	100 / 100	598 ms	157792 KiB

race

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

#define edge(xxxx,yyyy) ((xxxx)*(m+5)+(yyyy))
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>((aaaa)-1))&1)
#define totbit(xxxx) (32-__builtin_clz(xxxx))
#define totbitll(xxxx) (64-__builtin_clzll(ll(xxxx)))

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=333333349;
const ll mod=1e9+7;
const ld eps=1e-5;
const ll maxn=50009;

ll depth[200009],dist[200009],child[200009],res,n,k;
vector<pll> g[200009];
map<ll,ll> cost[200009];

void dfs(ll x,ll y) {
    //cout<<"!"<<x<<'\n';
    depth[x]=depth[y]+1;
    child[x]=1;
    for (pii ii:g[x]) {
        if (ii.fi!=y) {
            dist[ii.fi]=dist[x]+ii.se;
            dfs(ii.fi,x);
            child[x]+=child[ii.fi];
        }
    }
}

void solve(ll x,ll y) {
    //cout<<"?"<<x<<'\n';
    ll cap=0;
    ll pos=0;
    for (pii ii:g[x]) {
        if (ii.fi!=y) {
            solve(ii.fi,x);
            if (child[ii.fi]>cap) {
                cap=child[ii.fi];
                pos=ii.fi;
            }
        }
    }
    if (pos==0) {
        cost[x][dist[x]]=depth[x];
        //cout<<dist[x]<<' '<<depth[x]<<'\n';
        //cout<<"-----------------\n";
        return;
    }
    swap(cost[x],cost[pos]);
    //for (map<ll,ll>::const_iterator ij=cost[x].begin();ij!=cost[x].end();ij++) {
        //cout<<ij->first<<' '<<ij->second<<'\n';
    //}
    //cout<<"a\n";
    for (pii ii:g[x]) {
        if (ii.fi!=y&&ii.fi!=pos) {
            for (map<ll,ll>::const_iterator ij=cost[ii.fi].begin();ij!=cost[ii.fi].end();ij++) {
                if (ij->second==0) continue;
                if (cost[x][k+2*dist[x]-(ij->first)]) res=min(res,(ij->second)+cost[x][k+2*dist[x]-(ij->first)]-2*depth[x]);
                //cout<<ij->first<<' '<<ij->second<<'\n';
            }
            for (map<ll,ll>::const_iterator ij=cost[ii.fi].begin();ij!=cost[ii.fi].end();ij++) {
                if (ij->second==0) continue;
                //if (cost[x][k+2*dist[x]-(ij->first)]) res=min(res,(ij->second)+cost[x][k+2*dist[x]-(ij->first)]-2*depth[x]);
                //cout<<ij->first<<' '<<ij->second<<'\n';
                if (!cost[x][(ij->first)]) cost[x][(ij->first)]=(ij->second);
                else cost[x][(ij->first)]=min((ij->second),cost[x][(ij->first)]);
            }
        }
    }
    if (cost[x][k+dist[x]]) res=min(res,cost[x][k+dist[x]]-depth[x]);
    if (cost[x][dist[x]]) cost[x][dist[x]]=min(cost[x][dist[x]],depth[x]);
    else cost[x][dist[x]]=depth[x];
    //cout<<dist[x]<<' '<<depth[x]<<'\n';
    //cout<<"-----------------\n";
    //cout<<"!"<<res<<'\n';
}

ll best_path(int _n,int _k,int h[][2],int l[]) {
    res=oo;
    n=_n;
    k=_k;
    for (ll i=0;i<n-1;i++) {
        g[h[i][0]+1].push_back({h[i][1]+1,l[i]});
        g[h[i][1]+1].push_back({h[i][0]+1,l[i]});
        //cout<<h[i][0]+1<<' '<<h[i][1]+1<<' '<<l[i]<<'\n';
    }
    dist[1]=0;
    dfs(1,1);

    for (ll i=1;i<=n;i++) {
        //cout<<depth[i]<<' ';
    }
    //cout<<'\n';
    for (ll i=1;i<=n;i++) {
        //cout<<dist[i]<<' ';
    }
    //cout<<'\n';

    solve(1,1);
    if (res==oo) return -1;
    else return res;
}

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