제출 #1365470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365470		tapilyoca	Traffic (IOI10_traffic)	C++20	100 / 100	339 ms	145224 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
template<typename T>
using vec = vector<T>;
using vll = vec<ll>;
using vvll = vec<vll>;
#define pb push_back

ll n, sum;
vll subtree_size;
vll ans;
vvll adj;

void dfs(ll u, ll p) {
    ll mx = -1;

    for(ll &v : adj[u]) {
        if(v==p) continue;
        dfs(v,u);
        subtree_size[u] += subtree_size[v];
        mx = max(mx, subtree_size[v]);
    }

    if(p != -1) {
        // also check the back edge
        mx = max(mx, sum - subtree_size[u]);
    }

    ans[u] = mx;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = N;
    subtree_size.assign(n,0ll);
    ans.assign(n,1e18);

    for(int i = 0; i < n; i++) {
        subtree_size[i] = pp[i];
        sum += pp[i];
    }

    adj.resize(n);

    for(int i = 0; i < n-1; i++) {
        ll u = S[i], v = D[i];
        adj[u].pb(v);
        adj[v].pb(u);
    }

    
    dfs(0,-1);
    pair<ll,ll> mn = {1e18,-1};
    for(int i = 0; i < n; i++) {
        mn = min(mn, {ans[i],i});
    }

    return mn.second;
}

• 서브태스크 1: 25 / 25
• 서브태스크 2: 25 / 25
• 서브태스크 3: 25 / 25
• 서브태스크 4: 25 / 25