제출 #1123639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123639		marinaluca	Traffic (IOI10_traffic)	C++20	100 / 100	794 ms	122536 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

/**
#pragma GCC optimize ("O3")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
**/
using namespace std;
//#define int long long
#define ll long long


constexpr int NMAX = (int) 1e6;

vector <int> ans[NMAX + 5];
ll lazy[NMAX + 5];
ll cp[NMAX + 5];
ll s, maxi;
int rez;

inline void dfs (int nod, int parent)
{
    ll maxi = 0;
    for (auto elem : ans[nod])
    {
            if (elem == parent)
                continue;
           dfs (elem, nod);
           lazy[nod] += lazy[elem];
           maxi = max (maxi, lazy[elem]);
       
    }
    cp[nod] = maxi;
}
int LocateCentre(int N,int pp[],int S[],int D[])
{
    maxi = 1e18;
    rez = -1;
    for (int i = 0; i < N; ++ i)
    {
        lazy[i] = pp[i];
        s += pp[i];
    }
    for (int i = 0; i < N - 1; ++ i)
    {
        ans[S[i]].push_back(D[i]);
        ans[D[i]].push_back(S[i]);
    }
    dfs (0, -1);
    for (int i = 0; i < N; ++ i)
    {
        cp[i] = max (cp[i], s - lazy[i]);
        if (cp[i] < maxi)
        {
            maxi = cp[i];
            rez = i;
        }
    }
    return rez;
    
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25