oj.uz

Submission #870981

# Submission time Handle Problem Language Result Execution time Memory
870981 2023-11-09T16:05:10 Z _uros9 Traffic (IOI10_traffic) C++17
0 / 100
 13 ms 36004 KB 
#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;
  	long long gg=3000000000000000;
    dfs(0,gg,rez,-1);
    /*for(int i=0; i<n; i++)
        cout << seg[i] << endl;
    int gg=3e15;
    cout << gg << endl;*/
    return rez;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35932 KB Output is correct
2 Correct 13 ms 35932 KB Output is correct
3 Correct 12 ms 36004 KB Output is correct
4 Incorrect 11 ms 35932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35932 KB Output is correct
2 Correct 13 ms 35932 KB Output is correct
3 Correct 12 ms 36004 KB Output is correct
4 Incorrect 11 ms 35932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35932 KB Output is correct
2 Correct 13 ms 35932 KB Output is correct
3 Correct 12 ms 36004 KB Output is correct
4 Incorrect 11 ms 35932 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 35932 KB Output is correct
2 Correct 13 ms 35932 KB Output is correct
3 Correct 12 ms 36004 KB Output is correct
4 Incorrect 11 ms 35932 KB Output isn't correct
5 Halted 0 ms 0 KB -