oj.uz

Submission #647564

# Submission time Handle Problem Language Result Execution time Memory
647564 2022-10-03T07:30:24 Z ymm Ideal city (IOI12_city) C++17
100 / 100
 254 ms 28236 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2664 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2660 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 5 ms 2900 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct
5 Correct 7 ms 3056 KB Output is correct
6 Correct 5 ms 3028 KB Output is correct
7 Correct 5 ms 3060 KB Output is correct
8 Correct 5 ms 3028 KB Output is correct
9 Correct 5 ms 3028 KB Output is correct
10 Correct 5 ms 3028 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6988 KB Output is correct
2 Correct 36 ms 7116 KB Output is correct
3 Correct 103 ms 13628 KB Output is correct
4 Correct 116 ms 13660 KB Output is correct
5 Correct 219 ms 24652 KB Output is correct
6 Correct 203 ms 24692 KB Output is correct
7 Correct 239 ms 24948 KB Output is correct
8 Correct 230 ms 24612 KB Output is correct
9 Correct 235 ms 24940 KB Output is correct
10 Correct 248 ms 28236 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7372 KB Output is correct
2 Correct 38 ms 7408 KB Output is correct
3 Correct 113 ms 14416 KB Output is correct
4 Correct 119 ms 14312 KB Output is correct
5 Correct 254 ms 26248 KB Output is correct
6 Correct 247 ms 25500 KB Output is correct
7 Correct 250 ms 26460 KB Output is correct
8 Correct 229 ms 25452 KB Output is correct
9 Correct 212 ms 25072 KB Output is correct
10 Correct 252 ms 25108 KB Output is correct