Submission #377761

#	Time	Username	Problem	Language	Result	Execution time	Memory
377761		AlexRex0	Traffic (IOI10_traffic)	C++14	100 / 100	1133 ms	142236 KiB

traffic

#include "traffic.h"
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
vector<int> g[1000002];
long long int sub[1000002];
bool visitado[1000002];
bool visitado2[1000002];
int v[1000002];
long long int dfs(int nodo, int padre){
    sub[nodo]+= v[nodo];
    for(int i = 0 ; i < g[nodo].size(); ++i){
        if(g[nodo][i] != padre){
            sub[nodo]+= dfs(g[nodo][i], nodo);
        }
    }
    return sub[nodo];
}
long long int indRes, indMax = -1, Max, aux, Res, ayuda;
static int N,P[1000000],S[1000000],D[1000000];
int LocateCentre(int N, int pp[], int S[], int D[]) {
    for(int i = 0; i < N - 1; ++i){
        g[S[i]].push_back(D[i]);
        g[D[i]].push_back(S[i]);
        v[i] = pp[i];
    }
    v[N - 1] = pp[N - 1];
    dfs(0, -1);
    Max = -1;
    for(int i = 0; i < g[0].size(); ++i){
        ayuda = sub[g[0][i]];
        if(ayuda > Max){
            Max = ayuda;
        }
    }
    Res = Max;
    visitado2[0] = true;
    while(true){
        Max = -1;
        for(int i = 0; i < g[aux].size(); ++i){
            ayuda = sub[g[aux][i]];
            if(ayuda > Max){
                Max = ayuda;
                indMax = g[aux][i];
            }
        }
        if(visitado2[indMax]){
            if(Max < Res){
                indRes = aux;
                Res = Max;
            }
            return indRes;
        }
        visitado2[indMax] = true;
        if(Max < Res){
            indRes = aux;
            Res = Max;
        }
        sub[aux]-= sub[indMax];
        sub[indMax]+= sub[aux];
        if(indRes == indMax){
            break;
        }
        aux = indMax;
    }
    return indRes;
}

Compilation message (stderr)

traffic.cpp: In function 'long long int dfs(int, int)':
traffic.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0 ; i < g[nodo].size(); ++i){
      |                     ~~^~~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < g[0].size(); ++i){
      |                    ~~^~~~~~~~~~~~~
traffic.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i = 0; i < g[aux].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~
traffic.cpp: At global scope:
traffic.cpp:20:36: warning: 'D' defined but not used [-Wunused-variable]
   20 | static int N,P[1000000],S[1000000],D[1000000];
      |                                    ^
traffic.cpp:20:25: warning: 'S' defined but not used [-Wunused-variable]
   20 | static int N,P[1000000],S[1000000],D[1000000];
      |                         ^
traffic.cpp:20:14: warning: 'P' defined but not used [-Wunused-variable]
   20 | static int N,P[1000000],S[1000000],D[1000000];
      |              ^
traffic.cpp:20:12: warning: 'N' defined but not used [-Wunused-variable]
   20 | static int N,P[1000000],S[1000000],D[1000000];
      |            ^

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