제출 #556406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556406		a_aguilo	Traffic (IOI10_traffic)	C++14	50 / 100	516 ms	229716 KiB

traffic

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

using namespace std;

void dfs(int nodo, int padre, vector<vector<int>>& listaAdy, vector<vector<int>>& lista2){
    for(int conexion: listaAdy[nodo]){
        if(conexion != padre){
            lista2[nodo].push_back(conexion);
            dfs(conexion, nodo, listaAdy, lista2);
        }
    }
}

long long int dfs2(int nodo, vector<vector<int>>& listaAdy, int pop[], vector<long long int>& dp){
    if(dp[nodo] != -1) return dp[nodo];
    dp[nodo] = pop[nodo];
    for(int conexion: listaAdy[nodo]){
        dp[nodo]+= dfs2(conexion, listaAdy, pop, dp);
    }
    return dp[nodo];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   vector<vector<int>> listaAdy(N);
   vector<vector<int>> listaAdy2(N);
   for(int i= 0; i < N-1; ++i){
        int a = S[i];
        int b = D[i];
        listaAdy[a].push_back(b);
   }
   dfs(0, -1, listaAdy, listaAdy2);
   vector<long long int> dp(N, -1);
   long long int SUM = dfs2(0, listaAdy2, pp, dp);
   pair<long long int, int> ans = make_pair(SUM+1, 0);
   for(int i = 0; i < N; ++i){
        long long int mas_concurrida = SUM - dp[i];//lo que viene del padre
        for(int conexion: listaAdy2[i]){
            mas_concurrida = max(mas_concurrida, dp[conexion]); //lo que viene de cada nodo
        }
        ans = min(ans, make_pair(mas_concurrida, i));
   }
   return ans.second;
}

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