Submission #549349

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
549349	2022-04-15 16:27:59	palilo	Traffic (IOI10_traffic)	C++17	0 / 100	0 ms	212 KiB

traffic

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 "traffic.h"
#include <bits/stdc++.h>
int LocateCentre(int n, int p[], int s[], int d[]) {
    using namespace std;
    vector<vector<int>> adj(n);
    for (int i = 0; i + 1 < n; ++i) {
        adj[s[i]].emplace_back(d[i]);
        adj[d[i]].emplace_back(s[i]);
    }
    auto dfs_rev_order = [&](int root) {
        vector<int> stk = {root}, ord(n);
        for (auto& u : ord) {
            u = stk.back();
            stk.pop_back();
            for (const auto& v : adj[u]) {
                adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
                stk.emplace_back(v);
            }
        }
        reverse(ord.begin(), ord.end());
        return ord;
    }(0);
    const auto total = accumulate(p, p + n, 0);
    vector<int> subtree_size(n);
    vector<int64_t> dp(n);
    for (const auto& u : dfs_rev_order) {
        for (const auto& v : adj[u]) {
            subtree_size[u] += subtree_size[v];
            dp[u] += subtree_size[v];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25