Submission #988914

#	Time	Username	Problem	Language	Result	Execution time	Memory
988914		Ice_man	Traffic (IOI10_traffic)	C++14	0 / 100	5 ms	31576 KiB

traffic

/**
 ____    ____    ____    __________________    ____    ____    ____
||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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25