Submission #870980

#	Time	Username	Problem	Language	Result	Execution time	Memory
870980		_uros9	Traffic (IOI10_traffic)	C++17	0 / 100	12 ms	35936 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> graf(1e6+9,vector<int>(0));
vector<long long> seg(1e6+9,0);
vector<bool> visited(1e6+9,0);
long long zb=0;
void pravi_seg(int node,int cale,vector<int>&niz){
    if(visited[node]) return;
    visited[node]=true;
    seg[node]=niz[node];
    for(auto x:graf[node])
        pravi_seg(x,node,niz);
    for(auto x:graf[node]){
        if(x==cale) continue;
        seg[node]+=seg[x];
    }
}
void dfs(int node,long long mini,int&rez,int cale){
    if(visited[node]) return;
    visited[node]=true;
    long long maxi=0;
    maxi=max(maxi,zb-seg[node]);
    for(auto x:graf[node]){
        if(x==cale) continue;
        maxi=max(maxi,seg[node]);
    }
    mini=min(mini,maxi);
    if(mini==maxi)
        rez=node;
    for(auto x:graf[node])
        dfs(x,mini,rez,node);
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    n=N;
    vector<int> niz(n);
    for(int i=0; i<n; i++){
        niz[i]=pp[i];
        zb+=niz[i];
    }
    for(int i=0; i<n-1; i++){
        int a=S[i],b=D[i];
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    if(n==1) return 0;
    pravi_seg(0,-1,niz);
    for(int i=0; i<visited.size(); i++)
        visited[i]=false;
    int rez=0;
    dfs(0,3e15,rez,-1);
    return rez;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<visited.size(); i++)
      |                  ~^~~~~~~~~~~~~~~

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