oj.uz

Submission #383630

# Submission time Handle Problem Language Result Execution time Memory
383630 2021-03-30T12:23:37 Z alireza_kaviani Ideal city (IOI12_city) C++11
100 / 100
 102 ms 17256 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define X				first
#define Y				second

const int MAXN = 2e5 + 10;
const ll INF = 1e18;
const ll MOD = 1e9;

ll n , par[MAXN] , sz[MAXN] , Sz[MAXN] , Par[MAXN];
ll ans;
vector<int> adj[MAXN];
vector<pii> vec;

int getInd(int x , int y){
	int ind = lower_bound(vec.begin() , vec.end() , pii(x , y)) - vec.begin();
	if(ind == n || vec[ind] != pii(x , y))	return -1;
	return ind;
}

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v;
	sz[v] += sz[u];
}

void DFS(int v , int p = -1){
	for(int u : adj[v]){
		if(u == p)	continue;
		DFS(u , v);
		Sz[v] += Sz[u];
	}
	ans += Sz[v] * (n - Sz[v]);
}

void solve(){
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	sort(vec.begin() , vec.end());
	for(int i = 0 ; i < n ; i++){
		adj[i].clear();
		int x = vec[i].X , y = vec[i].Y;
		int ind = getInd(x , y - 1);
		if(ind == -1)	continue;
		Union(i , ind);
	}
	for(int i = 0 ; i < MAXN ; i++)	Sz[i] = sz[i] , Par[i] = Find(i);
	for(int i = 0 ; i < n ; i++){
		int x = vec[i].X , y = vec[i].Y;
		int ind = getInd(x - 1 , y);
		if(ind == -1)	continue;
		if(Find(ind) == Find(i))	continue;
		adj[Par[ind]].push_back(Par[i]);
		adj[Par[i]].push_back(Par[ind]);
		Union(i , ind);
	}
	DFS(Find(0));
}

ll DistanceSum(int N, int *X, int *Y) {
	n = N;
	ll mnx = INF , mny = INF;
	for(int i = 0 ; i < N ; i++){
		mnx = min(mnx , (ll)X[i]);
		mny = min(mny , (ll)Y[i]);
	}
	for(int i = 0 ; i < N ; i++){
		X[i] -= mnx; Y[i] -= mny;
	}
	for(int i = 0 ; i < N ; i++)	vec.push_back({X[i] , Y[i]});
	solve(); vec = {};
	for(int i = 0 ; i < N ; i++)	vec.push_back({Y[i] , X[i]});
	solve();
	return ans % MOD;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11752 KB Output is correct
2 Correct 22 ms 11880 KB Output is correct
3 Correct 44 ms 12268 KB Output is correct
4 Correct 43 ms 12268 KB Output is correct
5 Correct 81 ms 13032 KB Output is correct
6 Correct 82 ms 13800 KB Output is correct
7 Correct 84 ms 14076 KB Output is correct
8 Correct 84 ms 13800 KB Output is correct
9 Correct 80 ms 14056 KB Output is correct
10 Correct 84 ms 17256 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12136 KB Output is correct
2 Correct 25 ms 12008 KB Output is correct
3 Correct 52 ms 13164 KB Output is correct
4 Correct 51 ms 12908 KB Output is correct
5 Correct 102 ms 15080 KB Output is correct
6 Correct 94 ms 14856 KB Output is correct
7 Correct 100 ms 15976 KB Output is correct
8 Correct 91 ms 14808 KB Output is correct
9 Correct 88 ms 14440 KB Output is correct
10 Correct 89 ms 14440 KB Output is correct