Submission #1109086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109086		aguss	Traffic (IOI10_traffic)	C++14	100 / 100	1080 ms	194460 KiB

traffic

#include <bits/stdc++.h>

#define _USE_MATH_DEFINES
#define INF LLONG_MAX
#define MOD 1000000007

#define endl "\n"
#define sp " "

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define f1(i, x) for(auto &i : x)
#define f2(i, x, j) for(ll i = j; i < x; i++)

#define raya() cout << endl << "====================================" << endl
#define dbg(x) cerr << #x << ": " << x << endl;

using namespace std;
using ll = long long;
ll sum = 0;
vector<vector<ll>> sum1, arr;
vector<ll> P;
vector<bool> vis;
ll dfs(int n){
    if(vis[n]) return 0;
    vis[n] = 1; 
    f1(i, arr[n]){
        int aux = dfs(i);
        if(aux){
            sum1[n].push_back(aux);
        }
    }
    int ans = 0;
    f1(i, sum1[n]){
        ans += i;
    }
    sum1[n].push_back(0);
    sum1[n].push_back(sum - ans - P[n]);
    return ans + P[n];
}
int LocateCentre(int n, int p[], int s[], int d[]){
    arr.assign(n, vector<ll>(0));
    sum1.assign(n, vector<ll>(0));
    f2(i, n, 0){
        P.push_back(p[i]);
        sum += P[i];
    }
    vis.assign(n, 0);
    f2(i, n - 1, 0){
        arr[s[i]].push_back(d[i]);
        arr[d[i]].push_back(s[i]);
    }
    int r = s[(n - 1) / 2];
    dfs(r);
    ll sans = -1, ans;
    f2(i, n, 0){
        ll aux = 0;
        f1(j, sum1[i]){
            aux = max(j, aux);
        }
        if(sans == -1){
            sans = aux;
            ans = i;
        }
        if(sans > aux){
            sans = aux;
            ans = i;
        } 
    }
    return ans;
}

Compilation message (stderr)

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

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