Submission #860997

#	Time	Username	Problem	Language	Result	Execution time	Memory
860997		KK_1729	Traffic (IOI10_traffic)	C++17	100 / 100	935 ms	162904 KiB

traffic

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

// #define int long long
#define double long long double
#define pb push_back
#define str string
#define vi vector<int>
#define mp make_pair
#define mi map<int, int>
#define umi unordered_map<int, int>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define all(a) a.begin(), a.end()
// #define endl "\n"

vector<vector<int>> graph;
vector<int> a;
vector<int> dp;
int calc(int x, int p = -1){
    if (dp[x]) return dp[x];
    int ans = a[x];
    for (auto item: graph[x]){
        if (item == p) continue;
        ans += calc(item, x);
    }
    return dp[x] = ans;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   int n = N;
   graph.resize(n);
   a.resize(n);
   int o = 0;
   FOR(i,0,n) a[i] = pp[i];
   for (auto x: a) o += x;
   dp.resize(n);
   FOR(i,0,n-1){
      int u = S[i];
      int v = D[i];
      graph[u].pb(v);
      graph[v].pb(u);
   }
   // cout << "i" << endl;
   stack<int> s;
   s.push(0);
   vector<int> visited(n);
   // cout << "i" << endl;
   calc(0);
   // cout << "i" << endl;
   vector<int> ans(n);
   while (!s.empty()){
       int current = s.top();
       s.pop();
       if (visited[current]) continue;
       int m = 0;
       int u = 0;
       for (auto x: graph[current]){
           if (visited[x]) continue;
           // parent[x] = current;
           m = max(m, dp[x]);
           u += dp[x];
           s.push(x);
           // if (current == 1) cout << x << endl;
       }
       // if (current == 1) cout << u << endl;
       ans[current] = max(m, o-u-a[current]);
       visited[current] = 1;
   }
   
   // cout << "i" << endl;
   int best = 1e10;
   int x = 0;
   // printVector(ans);
   FOR(i,0,n){
       if (ans[i] < best){
           best = ans[i];
           x = i;
           // cout << i << endl;
       }
   }
   // printVector(dp);
   return x;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:72:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+10' to '2147483647' [-Woverflow]
   72 |    int best = 1e10;
      |               ^~~~

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