Submission #289738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
289738	2020-09-03T01:21:53 Z	b00n0rp	Ideal city (IOI12_city)	C++17	100 / 100	215 ms	19832 KB

city

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

#define pii pair<int,int>
#define F first
#define S second
#define pb push_back

const int MAXN = 100005;
const int MOD = 1000000000;

long long ans = 0;

int n;
pii a[MAXN];
set<int> adj[MAXN];
long long sz[MAXN],dist[MAXN],dp[MAXN];

int comp;

map<pair<int,int>,int> C;

void dfs(int u,int p){
	for(auto v:adj[u]){
		if(v != p){
			dfs(v,u);
			dp[v] += sz[v];
			sz[u] += sz[v];
			dp[u] += dp[v];
		}
	}
	for(auto v:adj[u]){
		if(v != p){
			ans += dp[v]*(sz[u]-sz[v]);
		}
	}
}

void solve(){
	C.clear();
	for(int i = 0; i < MAXN; i ++){
		adj[i].clear();
		sz[i] = 0;
		dp[i] = 0;
	}
	comp = 0;
	sort(a,a+n);
	C[a[0]] = 0;
	int last = 0;
	for(int i = 1; i < n; i++){
		if(a[i].F == a[i-1].F and a[i].S == a[i-1].S+1){
			C[a[i]] = comp;
		}
		else{
			sz[comp] = i-last;

			comp++;
			last = i;
			C[a[i]] = comp;
		}
	}
	sz[comp] = n-last;

	for(int i = 0; i < n; i++){
		if(C.find({a[i].F-1,a[i].S}) != C.end()){
			adj[C[{a[i].F-1,a[i].S}]].insert(C[{a[i].F,a[i].S}]);
			adj[C[{a[i].F,a[i].S}]].insert(C[{a[i].F-1,a[i].S}]);
		}
	}
	dfs(0,0);
}

int DistanceSum(int N, int *X, int *Y) {
	n = N;
	for(int i = 0; i < n; i ++){
		a[i] = {X[i],Y[i]};
	}
	solve();
	for(int i = 0; i < n; i ++){
		a[i] = {Y[i],X[i]};
	}
	solve();
	return ans%MOD;
}

Subtask #1

11.0 / 11.0

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

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	6784 KB	Output is correct
2	Correct	7 ms	6656 KB	Output is correct
3	Correct	8 ms	6784 KB	Output is correct
4	Correct	8 ms	6784 KB	Output is correct
5	Correct	8 ms	6784 KB	Output is correct
6	Correct	8 ms	6784 KB	Output is correct
7	Correct	10 ms	6784 KB	Output is correct
8	Correct	8 ms	6784 KB	Output is correct
9	Correct	8 ms	6784 KB	Output is correct
10	Correct	8 ms	6816 KB	Output is correct

Subtask #3

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	8192 KB	Output is correct
2	Correct	41 ms	8312 KB	Output is correct
3	Correct	104 ms	10640 KB	Output is correct
4	Correct	100 ms	10744 KB	Output is correct
5	Correct	205 ms	14712 KB	Output is correct
6	Correct	205 ms	14712 KB	Output is correct
7	Correct	215 ms	14840 KB	Output is correct
8	Correct	207 ms	14544 KB	Output is correct
9	Correct	205 ms	15096 KB	Output is correct
10	Correct	194 ms	19832 KB	Output is correct

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	8952 KB	Output is correct
2	Correct	41 ms	8952 KB	Output is correct
3	Correct	99 ms	12940 KB	Output is correct
4	Correct	101 ms	12280 KB	Output is correct
5	Correct	198 ms	19080 KB	Output is correct
6	Correct	210 ms	17016 KB	Output is correct
7	Correct	201 ms	19448 KB	Output is correct
8	Correct	203 ms	17016 KB	Output is correct
9	Correct	206 ms	16520 KB	Output is correct
10	Correct	205 ms	16504 KB	Output is correct