Submission #758928

#	Time	Username	Problem	Language	Result	Execution time	Memory
758928		raysh07	Traffic (IOI10_traffic)	C++17	100 / 100	1035 ms	183868 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn = 1e6 + 69;
int n;
int a[maxn], dep[maxn];
vector <int> adj[maxn];
long long dp[maxn], sub[maxn];

void dfs(int u, int par){
    sub[u] = a[u];
    for (int v : adj[u]){
        if (v == par) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        sub[u] += sub[v];
    }
}

void dfs2(int u, int par){
    for (int v : adj[u]){
        if (v == par) continue;
        dp[v] = dp[u] - sub[v] + sub[1] - sub[v];
        dfs2(v, u);
    }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {  
    n = N;
    for (int i = 1; i <= n; i++) a[i] = pp[i - 1];
    for (int i = 0; i < n - 1; i++){
        int u = S[i];
        int v = D[i];
        u++; v++;
        
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    pair<long long, int> ans = make_pair(1e18, -1);
    
    for (int i = 1; i <= 1; i++){
        dep[i] = 0;
        dfs(i, -1);
        
        long long val = 0;
        for (int j = 1; j <= n; j++){
            val += 1LL * dep[j] * a[j];
        }
        dp[i] = val;
    }
    
    dfs2(1, -1);
    
    for (int i = 1; i <= n; i++) ans = min(ans, make_pair(dp[i], i));
    
    return ans.second - 1;
}

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