Submission #1260640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260640		PlayVoltz	Ideal city (IOI12_city)	C++20	100 / 100	80 ms	16180 KiB

city

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

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int MOD = 1000000000;

int n, ans=0;
vector<int> sz;
vector<vector<int> > graph;

void dfs(int node, int p){
	for (auto num:graph[node])if (num!=p)dfs(num, node), sz[node]+=sz[num], ans=(ans+sz[num]*(n-sz[num]))%MOD;
}

void calc(map<int, vector<int> > ord){
	graph.clear();
	sz.clear();
	sz.resize(n+1, 0);
	graph.resize(n+1);
	int counter=0;
	map<int, int> prev, now;
	for (auto [c, vect]:ord){
		sort(vect.begin(), vect.end());
		for (int i=0; i<vect.size(); ++i){
			if (!i||vect[i]!=vect[i-1]+1)++counter;
			now[vect[i]]=counter;
			++sz[counter];
			if (prev[vect[i]])if (graph[counter].empty()||graph[counter].back()!=prev[vect[i]])graph[counter].pb(prev[vect[i]]), graph[prev[vect[i]]].pb(counter);
		}
		swap(prev, now);
		now.clear();
	}
	dfs(1, -1);
}

signed DistanceSum(signed N, signed *x, signed *y){
	n=N;
	map<int, vector<int> > a, b;
	for (int i=0; i<n; ++i)a[x[i]].pb(y[i]), b[y[i]].pb(x[i]);
	calc(a);
	calc(b);
	return (signed)ans;
}

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