oj.uz

Submission #878978

# Submission time Handle Problem Language Result Execution time Memory
878978 2023-11-25T22:56:18 Z AverageAmogusEnjoyer Traffic (IOI10_traffic) C++17
0 / 100
 9 ms 29188 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e6;
vector<int> adj[N];
ll dp[N];
ll sum[N];
void dfs0(int u=0,int e=-1) {
    for (int &v: adj[u]) if (v!=e) {
        dfs0(v,u);
        cmax(dp[u],sum[v]);
        sum[u]+=sum[v];
    }
}
void dfs1(int u=0,int e=-1) {
    for (int &v: adj[u]) if (v!=e) {
        cmax(dp[v],dp[0]-sum[v]);
        dfs1(v,u);
    }
}
int LocateCentre(int n, int _w[], int s[], int e[]) {
    for (int i=0;i<n-1;i++) {
        adj[s[i]].push_back(e[i]);
        adj[e[i]].push_back(s[i]);
    }
    for (int i=0;i<n;i++) {
        sum[i]=_w[i];
    }
    dfs0();
    dfs1();
    ll mx = 1e18;
    int res = -1;
    for (int i=0;i<n;i++) {
        if (cmin(mx,dp[i])) {
            res = i;
        }
    }
    assert(res!=-1);
    return res;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Incorrect 6 ms 29188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Incorrect 6 ms 29188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Incorrect 6 ms 29188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Incorrect 6 ms 29188 KB Output isn't correct
4 Halted 0 ms 0 KB -