Submission #556312

# Submission time Handle Problem Language Result Execution time Memory
556312 2022-05-02T20:40:46 Z a_aguilo Traffic (IOI10_traffic) C++14
0 / 100
0 ms 304 KB
#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= 1; i < N; ++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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 304 KB Output isn't correct
2 Halted 0 ms 0 KB -