oj.uz

답안 #982375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
982375 2024-05-14T07:40:32 Z Godgift42 경주 (Race) (IOI11_race) C++17
43 / 100
 3000 ms 43648 KB 
#include <bits/stdc++.h>
using namespace std;


vector<vector<pair<int,int>>> adj;
int n, k;
vector<int> subtr;
vector<bool> vis;
unordered_map<int,int> mp;
int ans=INT_MAX;

void findsize(int u, int p){
    subtr[u]=1;
    for(auto [v,w]:adj[u]){
        if(v!=p and !vis[v]){
            findsize(v,u);
            subtr[u]+=subtr[v];
        }
    }
}

int findcentroid(int u, int p, int sz){
    for(auto [v,w]:adj[u]){
        if(v!=p and !vis[v] and subtr[v]>sz/2)return findcentroid(v,u,sz);
    }
    return u;
}

void dfs1(int u, int p, int dist, int depth){
    if(dist>k)return;
    if(mp[k-dist] or k==dist) ans=min(ans,mp[k-dist]+depth);
    for(auto [v,w]:adj[u]){
        if(v!=p and !vis[v]){
            dfs1(v,u,dist+w,depth+1);
        }
    }
}

void dfs2(int u, int p, int dist, int depth){
    if(dist>k)return;
    if(mp[dist]==0)mp[dist]=depth;
    else mp[dist]=min(mp[dist],depth);
    for(auto [v,w]:adj[u]){
        if(v!=p and !vis[v]){
            dfs2(v,u,dist+w,depth+1);
        }
    }
}

void buildcentroid(int u, int p){
    findsize(u,u);
    int c=findcentroid(u,u,subtr[u]);
    vis[c]=true;
    for(auto [v,w]:adj[c]){
        if(v!=p and !vis[v]){
            dfs1(v,c,w,1);
            dfs2(v,c,w,1);
        }
    }
    mp.clear();
    for(auto [v,w]:adj[c]){
        if(!vis[v])buildcentroid(v,c);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n=N;
    k=K;
    adj.resize(n);
    subtr.resize(n);
    vis.resize(n);
    for(int i=0;i<n-1;i++){
        adj[H[i][1]].push_back({H[i][0],L[i]});
        adj[H[i][0]].push_back({H[i][1],L[i]});
    }
    buildcentroid(0,-1);
    if(ans==INT_MAX)return -1;
    return ans;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2620 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2620 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Correct 2 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2496 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 2 ms 2396 KB Output is correct
29 Correct 3 ms 2392 KB Output is correct
30 Correct 2 ms 2392 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 2 ms 2396 KB Output is correct
33 Correct 2 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 2 ms 2396 KB Output is correct
38 Correct 2 ms 2396 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2620 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 106 ms 11244 KB Output is correct
20 Correct 120 ms 12188 KB Output is correct
21 Correct 107 ms 11876 KB Output is correct
22 Correct 104 ms 12548 KB Output is correct
23 Correct 56 ms 12628 KB Output is correct
24 Correct 46 ms 12384 KB Output is correct
25 Correct 100 ms 15092 KB Output is correct
26 Correct 91 ms 17444 KB Output is correct
27 Correct 132 ms 19092 KB Output is correct
28 Correct 182 ms 30724 KB Output is correct
29 Correct 187 ms 30056 KB Output is correct
30 Correct 127 ms 19724 KB Output is correct
31 Correct 125 ms 19932 KB Output is correct
32 Correct 138 ms 19672 KB Output is correct
33 Correct 178 ms 18656 KB Output is correct
34 Correct 108 ms 19132 KB Output is correct

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2620 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Correct 1 ms 2392 KB Output is correct
21 Correct 2 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2496 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 2 ms 2396 KB Output is correct
29 Correct 3 ms 2392 KB Output is correct
30 Correct 2 ms 2392 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 2 ms 2396 KB Output is correct
33 Correct 2 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 2 ms 2396 KB Output is correct
38 Correct 2 ms 2396 KB Output is correct
39 Correct 106 ms 11244 KB Output is correct
40 Correct 120 ms 12188 KB Output is correct
41 Correct 107 ms 11876 KB Output is correct
42 Correct 104 ms 12548 KB Output is correct
43 Correct 56 ms 12628 KB Output is correct
44 Correct 46 ms 12384 KB Output is correct
45 Correct 100 ms 15092 KB Output is correct
46 Correct 91 ms 17444 KB Output is correct
47 Correct 132 ms 19092 KB Output is correct
48 Correct 182 ms 30724 KB Output is correct
49 Correct 187 ms 30056 KB Output is correct
50 Correct 127 ms 19724 KB Output is correct
51 Correct 125 ms 19932 KB Output is correct
52 Correct 138 ms 19672 KB Output is correct
53 Correct 178 ms 18656 KB Output is correct
54 Correct 108 ms 19132 KB Output is correct
55 Correct 21 ms 3420 KB Output is correct
56 Correct 11 ms 3164 KB Output is correct
57 Correct 86 ms 11564 KB Output is correct
58 Correct 32 ms 12240 KB Output is correct
59 Correct 2282 ms 23388 KB Output is correct
60 Execution timed out 3011 ms 43648 KB Time limit exceeded
61 Halted 0 ms 0 KB -