oj.uz

Submission #126447

# Submission time Handle Problem Language Result Execution time Memory
126447 2019-07-07T18:44:21 Z jaaguptamme Race (IOI11_race) C++14
9 / 100
 172 ms 68088 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#include "race.h"
using namespace std;
const ll CN=1000005;
vector<pii>g[CN];
map<ll,ll>*mp[CN];
ll dist[CN],sz[CN],dep[CN];
ll res=INT_MAX;
ll k;
void dfs(ll u,ll prev){
    sz[u]=1;
    ll mxsz=-1,mxn=-1;
    for(auto el:g[u]){
        ll v=el.first;
        ll c=el.second;
        if(v==prev)continue;
        dist[v]=dist[u]+c;
        dep[v]=dep[u]+1;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>mxsz){
            mxsz=sz[v];
            mxn=v;
        }
    }
    if(mxsz!=-1)mp[u]=mp[mxn];
    else mp[u]=new map<ll,ll>();
    if((*mp[u]).count(dist[u]))(*mp[u])[dist[u]]=min((*mp[u])[dist[u]],dep[u]);
    else (*mp[u])[dist[u]]=dep[u];
    if((*mp[u]).count(k+dist[u])){
        ll node=(*mp[u])[k+dist[u]];
        //cout<<"CHANG"<<k-dist[u]<<' '<<node<<' '<<dep[u]<<' '<<u<<'\n';
        res=min(res,abs(node-dep[u]));
    }

    for(auto E:g[u]){
        ll v=E.first;
        if(v==prev ||v==mxn)continue;
        for(auto el:(*mp[v])){
            ll nx=el.first;
             ll de=el.second;
             if((*mp[u]).count(k-nx)){
                ll node=(*mp[u])[k-nx];
                res=min(res,abs(de-dep[u])+abs(dep[u]-node));
               // cout<<"CHANGE"<<nx<<' '<<k<<' '<<de<<' '<<res<<'\n';
             }
        }
        for(auto el:(*mp[v])){
            ll nx=el.first;
             ll de=el.second;
             if((*mp[u]).count(nx)){
                 (*mp[u])[nx]=min((*mp[u])[nx],de);
             }else  (*mp[u])[nx]=de;
        }
    }
    /*
    cout<<"NODE";
    cout<<u<<' '<<prev<<' '<<dist[u]<<' '<<dep[u]<<'\n';
    for(auto el:(*mp[u]))cout<<el.first<<' '<<el.second<<'\n';
    */
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<N-1;i++){
        ll u,v,c;u=H[i][0];
        v=H[i][1];
        c=L[i];
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    for(int i=0;i<CN;i++){
        dep[i]=0;
        dist[i]=0;
        sz[i]=0;
    }
    dep[1]=0;
    dfs(1,N);
    int ans=res;
    if(ans<=N)return ans;
    else return -1;
}
/*
int main(){
    int n=4;
    int k=7;
    int h[][2]={{0,1},{1,2},{1,3}};
    int l[]={1,2,4};
    std::cout<<best_path(n,k,h,l)<<'\n';
}
*/
/*
int main(){
    int n=11;
    int k=12;
    int h[][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
    int l[]={3,4,5,4,6,3,2,5,6,7};
    cout<<best_path(n,k,h,l)<<'\n';
}
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 47 ms 47384 KB Output is correct
5 Correct 52 ms 47360 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 52 ms 47352 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47324 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 44 ms 47312 KB Output is correct
12 Correct 44 ms 47352 KB Output is correct
13 Correct 44 ms 47352 KB Output is correct
14 Correct 44 ms 47352 KB Output is correct
15 Correct 43 ms 47356 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 43 ms 47480 KB Output is correct
18 Correct 44 ms 47368 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 47 ms 47384 KB Output is correct
5 Correct 52 ms 47360 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 52 ms 47352 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47324 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 44 ms 47312 KB Output is correct
12 Correct 44 ms 47352 KB Output is correct
13 Correct 44 ms 47352 KB Output is correct
14 Correct 44 ms 47352 KB Output is correct
15 Correct 43 ms 47356 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 43 ms 47480 KB Output is correct
18 Correct 44 ms 47368 KB Output is correct
19 Incorrect 43 ms 47352 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 47 ms 47384 KB Output is correct
5 Correct 52 ms 47360 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 52 ms 47352 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47324 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 44 ms 47312 KB Output is correct
12 Correct 44 ms 47352 KB Output is correct
13 Correct 44 ms 47352 KB Output is correct
14 Correct 44 ms 47352 KB Output is correct
15 Correct 43 ms 47356 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 43 ms 47480 KB Output is correct
18 Correct 44 ms 47368 KB Output is correct
19 Incorrect 172 ms 68088 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 47 ms 47384 KB Output is correct
5 Correct 52 ms 47360 KB Output is correct
6 Correct 44 ms 47352 KB Output is correct
7 Correct 52 ms 47352 KB Output is correct
8 Correct 44 ms 47352 KB Output is correct
9 Correct 44 ms 47324 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 44 ms 47312 KB Output is correct
12 Correct 44 ms 47352 KB Output is correct
13 Correct 44 ms 47352 KB Output is correct
14 Correct 44 ms 47352 KB Output is correct
15 Correct 43 ms 47356 KB Output is correct
16 Correct 44 ms 47352 KB Output is correct
17 Correct 43 ms 47480 KB Output is correct
18 Correct 44 ms 47368 KB Output is correct
19 Incorrect 43 ms 47352 KB Output isn't correct
20 Halted 0 ms 0 KB -