oj.uz

Submission #126440

# Submission time Handle Problem Language Result Execution time Memory
126440 2019-07-07T18:22:06 Z jaaguptamme Race (IOI11_race) C++17
9 / 100
 136 ms 28188 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#include "race.h"
using namespace std;
const ll N=200005;
vector<pii>g[N];
map<ll,ll>*mp[N];
ll dist[N],sz[N],dep[N];
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});
    }
    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 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5100 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 7 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 7 ms 5112 KB Output is correct
18 Correct 7 ms 5112 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5100 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 7 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 7 ms 5112 KB Output is correct
18 Correct 7 ms 5112 KB Output is correct
19 Incorrect 6 ms 4980 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5100 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 7 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 7 ms 5112 KB Output is correct
18 Correct 7 ms 5112 KB Output is correct
19 Incorrect 136 ms 28188 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5100 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 7 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 7 ms 5112 KB Output is correct
18 Correct 7 ms 5112 KB Output is correct
19 Incorrect 6 ms 4980 KB Output isn't correct
20 Halted 0 ms 0 KB -