Submission #1125284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125284		SulA	Traffic (IOI10_traffic)	C++20	100 / 100	1016 ms	153052 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include "traffic.h"
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

vector<int> adj[1'000'000];
long long sum[1'000'000], dp[1'000'000], out[1'000'000];

void dfs(int u = 0, int p = -1) {
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        sum[u] += sum[v];
        dp[u] += dp[v] + sum[v];
    }
}

void dfs2(int u = 0, int p = -1) {
    for (int v : adj[u]) if (v != p) {
        out[v] = (out[u] + dp[u]) - (dp[v] + sum[v]) + (sum[0] - sum[v]);
        dfs2(v, u);
    }
}

int LocateCentre(int n, int* p, int* s, int* d) {
    for (int i = 0; i < n; i++)
        sum[i] = p[i];
    for (int i = 0; i < n - 1; i++) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    dfs();
    dfs2();
    pair<long long, int> ans{1e18, 1e9};
    for (int i = 0; i < n; i++)
        ans = min(ans, make_pair(dp[i] + out[i], i));
    return ans.second;
}

//signed main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    cout.tie(nullptr);
//
//    int n; cin >> n;
//    vector<int> p(n), s(n), d(n);
//    for (int i = 0; i < n; cin >> p[i++]);
//    for (int i = 0; i < n-1; cin >> d[i] >> s[i++]);
//    cout << LocateCentre(n, p, s, d);
//}

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