Submission #550164

#	Time	Username	Problem	Language	Result	Execution time	Memory
550164		AJ00	Traffic (IOI10_traffic)	C++14	100 / 100	951 ms	186364 KiB

traffic

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

const int MAXN =  1000001;
long long int s[MAXN],pp[MAXN],maxm[MAXN];
int n;
vector<int> adj[MAXN];
void dfs(int x, int p = 1){
    s[x] = maxm[x] = 0;
    for (int c: adj[x]){
        if (c != p){
           // cout << c << "\n";
            dfs(c,x);
            maxm[x] = max(maxm[x],pp[c]+s[c]);
            s[x] += pp[c]+s[c];
        }
    }
 //   cout << x << " " << s[x] << "\n";
}
int LocateCentre(int N, int P[], int S[], int D[]){
    n = N;
    int ans;
    for (int i = 0; i < n-1; i++){
        S[i]++;
        D[i]++;
        //cout << S[i] << " " << D[i] << "\n";
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
        pp[i+1] = P[i];
    }
    pp[n] = P[n-1]; 
    dfs(1);
    long long int cur = 1e18;
    for (int i = 1; i <= n; i++){
        if (cur > max(s[1]+pp[1]-s[i]-pp[i],maxm[i])){
            ans = i;
            cur = max(s[1]+pp[1]-s[i]-pp[i],maxm[i]);
        }
    }
    ans--;
    return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:41:8: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     ans--;
      |     ~~~^~

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