Submission #1144822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144822		sano	Traffic (IOI10_traffic)	C++20	100 / 100	733 ms	153004 KiB

traffic

#include "traffic.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 1000000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

vec<vec<ll>> g;

vec<ll> pod;

ll dfs(ll x, ll pr = -1) {
	trav(i, g[x]) {
		if (i == pr) continue;
		pod[x] += dfs(i, x);
	}
	return pod[x];
}

ll mini = NEK;
ll minipoz = -1;

void dfs2(ll x, ll h = 0, ll pr = -1) {
	ll mx = h;
	trav(i, g[x]) {
		if (i == pr) continue;
		mx = max(mx, pod[i]);
		dfs2(i, h + pod[x] - pod[i], x);
	}
	if (mx < mini) {
		mini = mx;
		minipoz = x;
	}
	return;
}

int LocateCentre(int n, int p[], int s[], int d[]) {
	pod.resize(n, 0);
	g.resize(n);
	For(i, (n - 1)) {
		g[s[i]].push_back(d[i]);
		g[d[i]].push_back(s[i]);
	}
	For(i, n) {
		pod[i] = p[i];
	}
	dfs(0);
	dfs2(0);
	return minipoz;
}

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