Submission #377719

#	Time	Username	Problem	Language	Result	Execution time	Memory
377719		Christopher_Rdz	Traffic (IOI10_traffic)	C++17	100 / 100	1155 ms	168428 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

int sub[1000002];
int peso[1000002];
vector <int> grafo[1000002];

void dfs(int nodo, int padre){
    for (int u: grafo[nodo]){
        if (u != padre){
            dfs(u, nodo);
            sub[nodo] += sub[u]; 
        }
    }
    sub[nodo] += peso[nodo];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    for (int i = 0; i < N - 1; i++){
        peso[i] = pp[i];
        grafo[S[i]].push_back(D[i]);
        grafo[D[i]].push_back(S[i]);
    }
    peso[N - 1] = pp[N - 1];
    int maximo = INT_MAX;
    int anterior = 0;
    int actual = 0;
    int aux = 0;
    int m;
    int res;
    dfs(0, -1);
    while (true){
        m = -1;
        anterior = actual;
        for (int u: grafo[anterior]){
            if (sub[u] > m){
                m = sub[u];
                actual = u;
            }
        }
        if (sub[actual] < maximo){
            maximo = sub[actual];
            res = actual;
        }else{
            res = actual;
            break;
        }
        sub[anterior] = sub[anterior] - sub[actual];
        sub[actual] = sub[actual] + sub[anterior];
    }
    return res;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:30:9: warning: unused variable 'aux' [-Wunused-variable]
   30 |     int aux = 0;
      |         ^~~

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