oj.uz

Submission #365439

# Submission time Handle Problem Language Result Execution time Memory
365439 2021-02-11T16:57:03 Z alexyd88 Traffic (IOI10_traffic) C++14
0 / 100
 5000 ms 23936 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 987654321
#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 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 18 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 28 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23788 KB Output is correct
13 Correct 18 ms 23788 KB Output is correct
14 Correct 20 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23916 KB Output is correct
17 Correct 18 ms 23788 KB Output is correct
18 Correct 17 ms 23936 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 16 ms 23788 KB Output is correct
21 Execution timed out 5089 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 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 18 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 28 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23788 KB Output is correct
13 Correct 18 ms 23788 KB Output is correct
14 Correct 20 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23916 KB Output is correct
17 Correct 18 ms 23788 KB Output is correct
18 Correct 17 ms 23936 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 16 ms 23788 KB Output is correct
21 Execution timed out 5089 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 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 18 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 28 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23788 KB Output is correct
13 Correct 18 ms 23788 KB Output is correct
14 Correct 20 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23916 KB Output is correct
17 Correct 18 ms 23788 KB Output is correct
18 Correct 17 ms 23936 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 16 ms 23788 KB Output is correct
21 Execution timed out 5089 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 16 ms 23788 KB Output is correct
2 Correct 18 ms 23788 KB Output is correct
3 Correct 18 ms 23788 KB Output is correct
4 Correct 16 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 28 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 17 ms 23788 KB Output is correct
13 Correct 18 ms 23788 KB Output is correct
14 Correct 20 ms 23788 KB Output is correct
15 Correct 16 ms 23788 KB Output is correct
16 Correct 16 ms 23916 KB Output is correct
17 Correct 18 ms 23788 KB Output is correct
18 Correct 17 ms 23936 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Correct 16 ms 23788 KB Output is correct
21 Execution timed out 5089 ms 23788 KB Time limit exceeded
22 Halted 0 ms 0 KB -