oj.uz

Submission #988914

# Submission time Handle Problem Language Result Execution time Memory
988914 2024-05-26T17:17:17 Z Ice_man Traffic (IOI10_traffic) C++14
0 / 100
 5 ms 31576 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include "traffic.h"
#include <map>
#include <vector>

#define maxn 1000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , ll> pil;
typedef pair <ll , int> pli;
typedef long double pd;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


ll dp[maxn] , sum[maxn];
vector <int> v[maxn];

void dfs(int node , int _par)
{
    for(int nb : v[node])
    {
        if(nb == _par)
            continue;
        dfs(nb , node);

        sum[node] += sum[nb];
        dp[node] = max(dp[node] , sum[node]);
    }
}


int LocateCentre(int N , int P[] , int S[] , int D[])
{
    ll _sum = 0LL;
    for(int i = 0; i < N; i++)
        _sum += P[i] , sum[i] = P[i];

    for(int i = 0; i < N - 1; i++)
        v[S[i]].pb(D[i]) , v[D[i]].pb(S[i]);

    dfs(0 , -1);

    for(int i = 0; i < N; i++)
        dp[i] = max(dp[i] , _sum - sum[i]);

    ll ans = 0;
    for(int i = 1; i < N; i++)
        if(dp[i] < dp[ans])
            ans = i;

    return ans;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31380 KB Output is correct
2 Correct 4 ms 31576 KB Output is correct
3 Correct 5 ms 31352 KB Output is correct
4 Incorrect 5 ms 31320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31380 KB Output is correct
2 Correct 4 ms 31576 KB Output is correct
3 Correct 5 ms 31352 KB Output is correct
4 Incorrect 5 ms 31320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31380 KB Output is correct
2 Correct 4 ms 31576 KB Output is correct
3 Correct 5 ms 31352 KB Output is correct
4 Incorrect 5 ms 31320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31380 KB Output is correct
2 Correct 4 ms 31576 KB Output is correct
3 Correct 5 ms 31352 KB Output is correct
4 Incorrect 5 ms 31320 KB Output isn't correct
5 Halted 0 ms 0 KB -