oj.uz

Submission #140697

# Submission time Handle Problem Language Result Execution time Memory
140697 2019-08-04T16:15:38 Z tmwilliamlin168 Ideal city (IOI12_city) C++14
100 / 100
 89 ms 10208 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5, M=1e9;
array<int, 2> a[mxN];
int n, c[mxN], d[mxN], s[mxN];
vector<int> adj[mxN];
ll ans;

ll dfs1(int u=0, int p=-1) {
	ll t=0;
	for(int v : adj[u]) {
		if(v==p)
			continue;
		t+=dfs1(v, u);
		s[u]+=s[v];
	}
	return t+s[u];
}

void dfs2(ll t, int u=0, int p=-1) {
	ans+=t*d[u];
	for(int v : adj[u])
		if(v^p)
			dfs2(t+n-2*s[v], v, u);
}

void solve(int *x, int *y) {
	for(int i=0; i<n; ++i)
		a[i]={x[i], y[i]};
	sort(a, a+n);
	int m=0;
	for(int i=0, j=0; i<n; i=j, ++m) {
		for(c[j++]=m; j<n&&a[j][0]==a[j-1][0]&&a[j][1]==a[j-1][1]+1; c[j++]=m);
		d[m]=s[m]=j-i;
	}
	for(int i=0; i<n; ++i) {
		int p=lower_bound(a, a+n, array<int, 2>{a[i][0]+1, a[i][1]})-a;
		if(p<n&&a[p][0]==a[i][0]+1&&a[p][1]==a[i][1]) {
			adj[c[i]].push_back(c[p]);
			adj[c[p]].push_back(c[i]);
		}
	}
	for(int i=0; i<m; ++i) {
		sort(adj[i].begin(), adj[i].end());
		adj[i].resize(unique(adj[i].begin(), adj[i].end())-adj[i].begin());
	}
	dfs2(dfs1()-n);
}

int DistanceSum(int N, int *x, int *y) {
	n=N;
	solve(x, y);
	for(int i=0; i<n; ++i)
		adj[i].clear();
	solve(y, x);
	return ans/2%M;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2780 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2712 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 6 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3576 KB Output is correct
2 Correct 18 ms 3832 KB Output is correct
3 Correct 39 ms 4728 KB Output is correct
4 Correct 40 ms 5112 KB Output is correct
5 Correct 76 ms 6904 KB Output is correct
6 Correct 80 ms 7928 KB Output is correct
7 Correct 78 ms 7672 KB Output is correct
8 Correct 77 ms 6740 KB Output is correct
9 Correct 79 ms 7544 KB Output is correct
10 Correct 86 ms 10208 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3708 KB Output is correct
2 Correct 19 ms 3832 KB Output is correct
3 Correct 45 ms 5240 KB Output is correct
4 Correct 43 ms 5240 KB Output is correct
5 Correct 89 ms 7672 KB Output is correct
6 Correct 84 ms 7604 KB Output is correct
7 Correct 89 ms 7672 KB Output is correct
8 Correct 86 ms 7672 KB Output is correct
9 Correct 83 ms 7288 KB Output is correct
10 Correct 82 ms 7416 KB Output is correct