Submission #291658

#	Time	Username	Problem	Language	Result	Execution time	Memory
291658		alexyd88	Traffic (IOI10_traffic)	C++14	0 / 100	16 ms	23808 KiB

traffic

#include "traffic.h"
#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 get g

vi adj[1000005];
int dp[1000005];
int dp2[1000005];
int gp[1000005];

int dfs (int l, int p)
{
    dp[l] = gp[l];
    for (auto it : adj[l])
        if (it != p)
            dp[l] += dfs(it, l);
    return dp[l];
}

void dfs2(int l, int p)
{
    if (p != -1)
        dp2[l] = dp2[p];
    for (auto it : adj[l])
        if (it != p)
            dfs(it, l);
}

int LocateCentre(int N, int P[1000005], int S[1000005], int D[1000005])
{
    for (int i = 0; i < N; i++)
        gp[i] = 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);
    dfs2(0, -1);
    int b = 0;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        if (dp[i] > b || dp2[i] > b)
        {
            ans = i;
            b = max(dp[i], dp2[i]);
        }
    }
    return ans;
}

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