oj.uz

Submission #556314

# Submission time Handle Problem Language Result Execution time Memory
556314 2022-05-02T20:51:16 Z a_aguilo Traffic (IOI10_traffic) C++14
0 / 100
 0 ms 212 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(dp[listaAdy2[0][0]], 0);
   for(int i = 1; i < listaAdy[0].size(); ++i) ans = max(ans, make_pair(dp[listaAdy[0][i]], 0));
   for(int i = 1; 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;
}

Compilation message

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int i = 1; i < listaAdy[0].size(); ++i) ans = max(ans, make_pair(dp[listaAdy[0][i]], 0));
      |                   ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -