제출 #553997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553997		a_aguilo	Traffic (IOI10_traffic)	C++14	0 / 100	1 ms	312 KiB

traffic

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

using namespace std;

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

int LocateCentre(int N, int pp[], int S[], int D[]) {
   vector<vector<int>> listaAdy(N);
   for(int i= 1; i < N; ++i){
        int a = S[i];
        int b = D[i];
        listaAdy[a].push_back(b);
   }
   vector<vector<int>> dp(N, vector<int> (N, -1));
   int act = -1e9;
    for(int conex: listaAdy[0]){
        act = max(act, dfs(0, conex, listaAdy, pp, dp));
    }
    pair<int, int> ans = make_pair(act, 0);
   for(int ciudad = 1; ciudad < N; ++ciudad){
        int act = -1e9;
        for(int conex: listaAdy[ciudad]){
            act = max(act, dfs(ciudad, conex, listaAdy, pp, dp));
        }
        ans = min(ans, make_pair(act, ciudad));
   }
   return ans.second;
}

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