Submission #758925

#	Time	Username	Problem	Language	Result	Execution time	Memory
758925		raysh07	Traffic (IOI10_traffic)	C++17	50 / 100	5088 ms	27920 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];

void dfs(int u, int par){
    for (int v : adj[u]){
        if (v == par) continue;
        dep[v] = dep[u] + 1;
        dfs(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 <= n; i++){
        dep[i] = 0;
        dfs(i, -1);
        
        long long val = 0;
        for (int j = 1; j <= n; j++){
            val += 1LL * dep[j] * a[j];
        }
        ans = min(ans, make_pair(val, i));
    }
    
    return ans.second - 1;
}

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