Submission #316343

#	Time	Username	Problem	Language	Result	Execution time	Memory
316343		vishnu_sujith	Traffic (IOI10_traffic)	C++17	100 / 100	1214 ms	176120 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#define LOG(...) cerr << "[" << #__VA_ARGS__ << "]: " << repr(__VA_ARGS__) << endl;
#define MSG(args) cerr << args << "\n";
#define debug(x) x
#else
#define LOG(...)
#define MSG(args)
#define debug(x)
#endif

#define mp make_pair
#define pb push_back
#define sz(x) (int)((x).size())
#define ms(x, v) memset((x), v, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define REP(x, n) for(int x = 0; x < n; x++)
#define REPV(x, v, n) for(int x = v; x < n; x++)
#define REVE(x, n) for(int x = n; x >= 0; x--)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;

vi adj[1000010];
ll tot_fans = 0, sze[1000010], cnt[1000010];

void dfs(int u, int parent, int P[])
{
    for(int v : adj[u]) if(v != parent)
    {
      dfs(v, u, P);
      sze[u] += sze[v];
      cnt[u] = max(cnt[u], sze[v]);
    }
    cnt[u] = max(cnt[u], tot_fans - sze[u] - P[u]);
    sze[u] += P[u];
}

int LocateCentre(int N, int P[], int S[], int D[])
{
    tot_fans = accumulate(P, P + N, 0LL);
    REP(i, N - 1)
		adj[S[i]].pb(D[i]), adj[D[i]].pb(S[i]);
    dfs(0, -1, P);
    return min_element(cnt, cnt + N) - cnt;
}

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