oj.uz

답안 #291658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291658 2020-09-05T15:24:27 Z alexyd88 Traffic (IOI10_traffic) C++14
0 / 100
 16 ms 23808 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -