oj.uz

Submission #964945

# Submission time Handle Problem Language Result Execution time Memory
964945 2024-04-17T18:20:13 Z Boomyday Traffic (IOI10_traffic) C++17
0 / 100
 3 ms 4444 KB 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#include "traffic.h"





vector<ll> nums; vector<vector<int>> adj;

ll mn = 1e18;
ll ans = -1;
ll sm = 0;

void dfs(int u, int p=-1){
    ll msz = -1;

    for(auto& v:adj[u]){
        if (v != p){
            dfs(v,u);
            nums[u] += nums[v];
            msz = max(msz,nums[v]);

        }
    }
    msz = max(msz,sm-nums[u]);
    if (msz < mn){
        mn = msz; ans = u;
    }

}


int LocateCentre(int n, int p[], int s[], int d[]) {
    nums.resize(n); adj.resize(n);

    for(int i=0;i<n;++i){ nums[i] = p[i]; sm += nums[i];}
    for(int i=0;i<n;++i) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    dfs(0);

    return ans;

}

/*
static int N,P[1000000],S[1000000],D[1000000];

int main(){
    int i;
    scanf("%d",&N);
    for (i=0;i<N;i++) scanf("%d",&P[i]);
    for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
    int r = LocateCentre(N,P,S,D);
    printf("%d\n",r);
    return 0;
}*/

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -