Submission #379296

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
379296	2021-03-17 22:03:48	justiny7	Race (IOI11_race)	C++17	100 / 100	1118 ms	38880 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 "race.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=2e5+1, INF=1e9;
int k, ans=INF, sz[mxN];
vector<pair<int, int>> adj[mxN], vals;
map<int, int> mn;
bool vis[mxN];
int dfs_sz(int v, int p=-1) {
    sz[v]=1;
    for (auto [u, d]:adj[v])
        if (!vis[u] && u^p)
            sz[v]+=dfs_sz(u, v);
    return sz[v];
}
int dfs_centroid(int tot, int v, int p=-1) {
    for (auto [u, d]:adj[v])
        if (!vis[u] && u^p && sz[u]*2>tot)
            return dfs_centroid(tot, u, v);
    return v;
}
void dfs(int v, int len, int p=-1, int dep=1) {
    vals.emplace_back(dep, len);
    for (auto [u, d]:adj[v])
        if (!vis[u] && u^p && len+d<=k)
            dfs(u, len+d, v, dep+1);
}
void decomp(int x=0) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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