oj.uz

Submission #944578

# Submission time Handle Problem Language Result Execution time Memory
944578 2024-03-13T01:10:07 Z irmuun Race (IOI11_race) C++17
100 / 100
 1716 ms 79688 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_bacK
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
const ll maxn=2e5+5;
 
int n=0;
set<pair<int,int> >adj[maxn];
vector<ll>sz(maxn),d(maxn);
 
void calc(int x,int p){
    n++;
    sz[x]=1;
    for(auto [y,w]:adj[x]){
        if(y!=p){
            calc(y,x);
            sz[x]+=sz[y];
        }
    }
}
 
int centroid(int x,int p){
    for(auto [y,w]:adj[x]){
        if(y==p) continue;
        if(sz[y]*2>n) return centroid(y,x);
    }
    return x;
}
 
void calc_dist(int x,int p){
    for(auto [y,w]:adj[x]){
        if(y!=p){
            d[y]=d[x]+w;
            calc_dist(y,x);
        }
    }
}
 
int best_path(int N,int K,int H[][2],int L[]){
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].insert({H[i][1],L[i]});
        adj[H[i][1]].insert({H[i][0],L[i]});
    }
    int ans=1e9;
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        n=0;
        calc(x,-1);
        int root=centroid(x,-1);
        map<ll,int>dist;
        map<ll,int>cur,clr;
        vector<pair<int,int>>v;
        function <void(int,int,int)> dfs=[&](int x,int p,int depth){
            if(cur[d[x]]==0){
                cur[d[x]]=depth;
            }
            else{
                cur[d[x]]=min(cur[d[x]],depth);
            }
            for(auto [y,w]:adj[x]){
                if(y!=p){
                    d[y]=d[x]+w;
                    dfs(y,x,depth+1);
                }
            }
        };
        for(auto [y,w]:adj[root]){
            cur=clr;
            d[y]=w;
            dfs(y,root,1);
            for(auto [i,val]:cur){
                if(i==K){
                    if(val>0){
                        ans=min(ans,val);
                    }
                }
                else if(i<K){
                    if(val>0&&dist[K-i]>0){
                        ans=min(ans,val+dist[K-i]);
                    }
                }
            }
            for(auto [i,val]:cur){
                if(dist[i]==0){
                    dist[i]=val;
                }
                else if(val>0){
                    dist[i]=min(dist[i],val);
                }
            }
        }
        for(auto [y,w]:adj[root]){
            adj[y].erase({root,w});
            q.push(y);
        }
        adj[root].clear();
    }
    if(ans==1e9) ans=-1;
    return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16560 KB Output is correct
3 Correct 4 ms 16472 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 5 ms 16576 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 4 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16576 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 5 ms 16476 KB Output is correct
12 Correct 4 ms 16472 KB Output is correct
13 Correct 4 ms 16476 KB Output is correct
14 Correct 4 ms 16652 KB Output is correct
15 Correct 4 ms 16476 KB Output is correct
16 Correct 4 ms 16476 KB Output is correct
17 Correct 4 ms 16476 KB Output is correct
18 Correct 4 ms 16476 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16560 KB Output is correct
3 Correct 4 ms 16472 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 5 ms 16576 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 4 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16576 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 5 ms 16476 KB Output is correct
12 Correct 4 ms 16472 KB Output is correct
13 Correct 4 ms 16476 KB Output is correct
14 Correct 4 ms 16652 KB Output is correct
15 Correct 4 ms 16476 KB Output is correct
16 Correct 4 ms 16476 KB Output is correct
17 Correct 4 ms 16476 KB Output is correct
18 Correct 4 ms 16476 KB Output is correct
19 Correct 4 ms 16472 KB Output is correct
20 Correct 4 ms 16476 KB Output is correct
21 Correct 6 ms 16568 KB Output is correct
22 Correct 8 ms 16728 KB Output is correct
23 Correct 6 ms 16732 KB Output is correct
24 Correct 6 ms 16732 KB Output is correct
25 Correct 6 ms 16732 KB Output is correct
26 Correct 6 ms 16640 KB Output is correct
27 Correct 5 ms 16476 KB Output is correct
28 Correct 6 ms 16848 KB Output is correct
29 Correct 6 ms 16728 KB Output is correct
30 Correct 6 ms 16732 KB Output is correct
31 Correct 6 ms 16732 KB Output is correct
32 Correct 6 ms 16732 KB Output is correct
33 Correct 7 ms 16732 KB Output is correct
34 Correct 6 ms 16732 KB Output is correct
35 Correct 6 ms 16752 KB Output is correct
36 Correct 6 ms 16732 KB Output is correct
37 Correct 6 ms 16744 KB Output is correct
38 Correct 7 ms 16876 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16560 KB Output is correct
3 Correct 4 ms 16472 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 5 ms 16576 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 4 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16576 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 5 ms 16476 KB Output is correct
12 Correct 4 ms 16472 KB Output is correct
13 Correct 4 ms 16476 KB Output is correct
14 Correct 4 ms 16652 KB Output is correct
15 Correct 4 ms 16476 KB Output is correct
16 Correct 4 ms 16476 KB Output is correct
17 Correct 4 ms 16476 KB Output is correct
18 Correct 4 ms 16476 KB Output is correct
19 Correct 350 ms 28180 KB Output is correct
20 Correct 307 ms 29300 KB Output is correct
21 Correct 378 ms 29000 KB Output is correct
22 Correct 337 ms 29524 KB Output is correct
23 Correct 453 ms 29776 KB Output is correct
24 Correct 210 ms 29520 KB Output is correct
25 Correct 292 ms 35572 KB Output is correct
26 Correct 115 ms 35236 KB Output is correct
27 Correct 554 ms 39428 KB Output is correct
28 Correct 1374 ms 70564 KB Output is correct
29 Correct 1503 ms 70112 KB Output is correct
30 Correct 526 ms 39760 KB Output is correct
31 Correct 482 ms 40220 KB Output is correct
32 Correct 677 ms 39880 KB Output is correct
33 Correct 939 ms 40272 KB Output is correct
34 Correct 1258 ms 57992 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16476 KB Output is correct
2 Correct 4 ms 16560 KB Output is correct
3 Correct 4 ms 16472 KB Output is correct
4 Correct 4 ms 16476 KB Output is correct
5 Correct 5 ms 16576 KB Output is correct
6 Correct 4 ms 16476 KB Output is correct
7 Correct 4 ms 16476 KB Output is correct
8 Correct 4 ms 16476 KB Output is correct
9 Correct 4 ms 16576 KB Output is correct
10 Correct 4 ms 16476 KB Output is correct
11 Correct 5 ms 16476 KB Output is correct
12 Correct 4 ms 16472 KB Output is correct
13 Correct 4 ms 16476 KB Output is correct
14 Correct 4 ms 16652 KB Output is correct
15 Correct 4 ms 16476 KB Output is correct
16 Correct 4 ms 16476 KB Output is correct
17 Correct 4 ms 16476 KB Output is correct
18 Correct 4 ms 16476 KB Output is correct
19 Correct 4 ms 16472 KB Output is correct
20 Correct 4 ms 16476 KB Output is correct
21 Correct 6 ms 16568 KB Output is correct
22 Correct 8 ms 16728 KB Output is correct
23 Correct 6 ms 16732 KB Output is correct
24 Correct 6 ms 16732 KB Output is correct
25 Correct 6 ms 16732 KB Output is correct
26 Correct 6 ms 16640 KB Output is correct
27 Correct 5 ms 16476 KB Output is correct
28 Correct 6 ms 16848 KB Output is correct
29 Correct 6 ms 16728 KB Output is correct
30 Correct 6 ms 16732 KB Output is correct
31 Correct 6 ms 16732 KB Output is correct
32 Correct 6 ms 16732 KB Output is correct
33 Correct 7 ms 16732 KB Output is correct
34 Correct 6 ms 16732 KB Output is correct
35 Correct 6 ms 16752 KB Output is correct
36 Correct 6 ms 16732 KB Output is correct
37 Correct 6 ms 16744 KB Output is correct
38 Correct 7 ms 16876 KB Output is correct
39 Correct 350 ms 28180 KB Output is correct
40 Correct 307 ms 29300 KB Output is correct
41 Correct 378 ms 29000 KB Output is correct
42 Correct 337 ms 29524 KB Output is correct
43 Correct 453 ms 29776 KB Output is correct
44 Correct 210 ms 29520 KB Output is correct
45 Correct 292 ms 35572 KB Output is correct
46 Correct 115 ms 35236 KB Output is correct
47 Correct 554 ms 39428 KB Output is correct
48 Correct 1374 ms 70564 KB Output is correct
49 Correct 1503 ms 70112 KB Output is correct
50 Correct 526 ms 39760 KB Output is correct
51 Correct 482 ms 40220 KB Output is correct
52 Correct 677 ms 39880 KB Output is correct
53 Correct 939 ms 40272 KB Output is correct
54 Correct 1258 ms 57992 KB Output is correct
55 Correct 35 ms 18332 KB Output is correct
56 Correct 20 ms 17496 KB Output is correct
57 Correct 149 ms 28244 KB Output is correct
58 Correct 63 ms 29536 KB Output is correct
59 Correct 495 ms 47184 KB Output is correct
60 Correct 1716 ms 79688 KB Output is correct
61 Correct 556 ms 40768 KB Output is correct
62 Correct 524 ms 40016 KB Output is correct
63 Correct 713 ms 39832 KB Output is correct
64 Correct 1652 ms 53988 KB Output is correct
65 Correct 1221 ms 55180 KB Output is correct
66 Correct 1684 ms 67656 KB Output is correct
67 Correct 318 ms 41920 KB Output is correct
68 Correct 1033 ms 58540 KB Output is correct
69 Correct 894 ms 53064 KB Output is correct
70 Correct 904 ms 53912 KB Output is correct