Submission #1024390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024390		socpite	Ideal city (IOI12_city)	C++17	0 / 100	181 ms	262144 KiB

city

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

const int maxn = 1e5+5;

const int mod = 1e9;

vector<int> g[maxn];
int W[maxn];

long long dfs(int x, int p, int N){
	long long re = 0;
	for(auto v: g[x]){
		if(v == p)continue;
		re += dfs(v, x, N);
		W[x] += W[v];
	}
	re += 1LL*W[x]*(N - W[x]);
	return re;
}

long long solve(int N, int *X, int *Y){
	for(int i = 1; i <= N; i++){
		g[i].clear();
		W[i] = 0;
	}
	int cnt = 0;
	map<int, vector<int>> mp;
	map<pair<int, int>, int> id;
	for(int i = 0; i < N; i++)mp[X[i]].push_back(Y[i]);
	for(auto v: mp){
		int prv = -2;
		for(auto pos: v.second){
			if(pos == prv + 1)id[{v.first, pos}] = cnt;
			else id[{v.first, pos}] = ++cnt;
			W[cnt]++;
			if(id.find({v.first-1, pos}) != id.end()){
				int prvid = id[{v.first-1, pos}];
				g[cnt].push_back(prvid);
				g[prvid].push_back(cnt);
			}
			prv = pos;
		}
	}
	for(int i = 1; i <= cnt; i++){
		sort(g[i].begin(), g[i].end());
		g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
	}
	return dfs(1, 0, N);
}


int DistanceSum(int N, int *X, int *Y) {
	long long ans = solve(N, X, Y);
	for(int i = 0; i < N; i++)swap(X[i], Y[i]);
	ans += solve(N, X, Y);
	return ans%mod;

}

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