Submission #321174

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
321174	2020-11-11 10:45:02	Kesatria_Komodo	Race (IOI11_race)	C++17	43 / 100	559 ms	41572 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
vector<pair<int , int>> adjlist[200001];
bool used[200001];
int subtree[200001];
int ans = 1e9 , target;
int cnt_subtree(int node , int bef){
    subtree[node] = 1;
    for (const pair<int , int> &it : adjlist[node])
        if (it.first != bef && !used[it.first])subtree[node] += cnt_subtree(it.first , node);
    return subtree[node];
}
int cari_centroid(int node , int bef , const int &max_bound){
    for (const pair<int , int> &it : adjlist[node])
        if (!used[it.first] && it.first != bef && subtree[it.first] > max_bound)
            return cari_centroid(it.first , node , max_bound);
    return node;
}
void dfs(int node , int bef , int depth , int val , int min_len[]){
    if (min_len[target - val])
        ans = min(ans , depth + min_len[target - val] - 2);
    for (const pair<int , int> &it : adjlist[node])
        if (it.first != bef && !used[it.first] && val + it.second <= target)
            dfs(it.first , node , depth + 1 , val + it.second , min_len);
    if (!min_len[val])
        min_len[val] = depth;
    else min_len[val] = min(min_len[val] , depth);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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