oj.uz

Submission #365442

# Submission time Handle Problem Language Result Execution time Memory
365442 2021-02-11T17:01:26 Z alexyd88 Traffic (IOI10_traffic) C++14
0 / 100
 5000 ms 23916 KB 
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define vvb vector<vector<bool>>
#define piii pair<int, pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define inf INT_MAX
#define pb push_back
#define p push
#define ll long long
#define ull unsigned long long
#define g get
#define dbl double
#define mn 1000005

int N, P[mn];
vi adj[mn];
int fans;
int ans[mn];

int dfs (int loc, int par)
{
    int sb = 0, mb = 0;
    for (auto i : adj[loc])
        if (i != par)
            sb += dfs(i, loc), mb = max(mb, dfs(i, loc));
    ans[loc] = max(mb, fans - sb - P[loc]);
    return sb + P[loc];
}

int LocateCentre(int fN, int fP[mn], int S[mn], int D[mn])
{
    N = fN;
    for (int i = 0; i < N; i++)
        P[i] = fP[i], fans += P[i];
    for (int i = 0; i < N - 1; i++)
        adj[S[i]].pb({D[i]}), adj[D[i]].pb({S[i]});
    dfs(0, -1);
    int bc = inf, bl;
    for (int i = 0; i < N; i++)
        if (bc > ans[i])
            bc = ans[i], bl = i;
    return bl;
}

/*int main(void)
{
    cout << "TR" << endl;
    int N, P[mn], S[mn], D[mn];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> P[i];
    for (int i = 0; i < N - 1; i++)
        cin >> S[i];
    for (int i = 0; i < N - 1; i++)
        cin >> D[i];
    cout << LocateCentre(N, P, S, D);
}*/

Compilation message

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:51:12: warning: 'bl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     return bl;
      |            ^~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 18 ms 23820 KB Output is correct
3 Correct 18 ms 23900 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 16 ms 23788 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 17 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 24 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 17 ms 23788 KB Output is correct
14 Correct 17 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 18 ms 23916 KB Output is correct
18 Correct 18 ms 23788 KB Output is correct
19 Correct 17 ms 23788 KB Output is correct
20 Correct 17 ms 23788 KB Output is correct
21 Execution timed out 5099 ms 23788 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 18 ms 23820 KB Output is correct
3 Correct 18 ms 23900 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 16 ms 23788 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 17 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 24 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 17 ms 23788 KB Output is correct
14 Correct 17 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 18 ms 23916 KB Output is correct
18 Correct 18 ms 23788 KB Output is correct
19 Correct 17 ms 23788 KB Output is correct
20 Correct 17 ms 23788 KB Output is correct
21 Execution timed out 5099 ms 23788 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 18 ms 23820 KB Output is correct
3 Correct 18 ms 23900 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 16 ms 23788 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 17 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 24 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 17 ms 23788 KB Output is correct
14 Correct 17 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 18 ms 23916 KB Output is correct
18 Correct 18 ms 23788 KB Output is correct
19 Correct 17 ms 23788 KB Output is correct
20 Correct 17 ms 23788 KB Output is correct
21 Execution timed out 5099 ms 23788 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 18 ms 23820 KB Output is correct
3 Correct 18 ms 23900 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 16 ms 23788 KB Output is correct
6 Correct 17 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 17 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 24 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 17 ms 23788 KB Output is correct
14 Correct 17 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23788 KB Output is correct
17 Correct 18 ms 23916 KB Output is correct
18 Correct 18 ms 23788 KB Output is correct
19 Correct 17 ms 23788 KB Output is correct
20 Correct 17 ms 23788 KB Output is correct
21 Execution timed out 5099 ms 23788 KB Time limit exceeded
22 Halted 0 ms 0 KB -