Submission #647564

#	Time	Username	Problem	Language	Result	Execution time	Memory
647564		ymm	Ideal city (IOI12_city)	C++17	100 / 100	254 ms	28236 KiB

city

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> A[N];
int sub_sz[N];
int weight_node[N];
int n;

int dfs1(int v, int p)
{
	sub_sz[v] = weight_node[v];
	for (int u : A[v]) {
		if (u != p)
			sub_sz[v] += dfs1(u, v);
	}
	return sub_sz[v];
}

ll dfs2(int v, int p)
{
	ll ans = 0;
	for (int u : A[v]) {
		if (u == p)
			continue;
		ans += (ll)sub_sz[u] * (n - sub_sz[u]);
		ans += dfs2(u, v);
	}
	return ans;
}

void make_tree(set<pii> nodes)
{
	Loop (i,0,N)
		A[i].clear();
	map<pii, int> col;
	int cnt = 0;
	for (pii v : nodes) {
		if (col.count(v))
			continue;
		weight_node[cnt] = 0;
		for (pii u = v; nodes.count(u); u.second++) {
			col[u] = cnt;
			weight_node[cnt]++;
			pii w = u; w.first -= 1;
			if (nodes.count(w)) {
				int c = col[w];
				if (!A[cnt].size() || A[cnt].back() != c) {
					A[c].push_back(cnt);
					A[cnt].push_back(c);
				}
			}
		}
		++cnt;
	}
	//for (pii v : nodes) {
	//	printf("col[%d, %d] = %d: ", v.first, v.second, col[v]);
	//	for (int u : A[col[v]])
	//		printf("%d ", u);
	//	printf("\n");
	//}
}

int DistanceSum(int N, int *X, int *Y)
{
	set<pii> s1, s2;
	Loop (i,0,N) {
		s1.insert({X[i], Y[i]});
		s2.insert({Y[i], X[i]});
	}
	::n = N;
	ll ans = 0;
	make_tree(s1);
	dfs1(0, -1);
	ans += dfs2(0, -1);
	make_tree(s2);
	dfs1(0, -1);
	ans += dfs2(0, -1);
	ans %= 1'000'000'000;
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45