oj.uz

Submission #382756

# Submission time Handle Problem Language Result Execution time Memory
382756 2021-03-28T07:02:23 Z Keshi Ideal city (IOI12_city) C++17
100 / 100
 63 ms 21792 KB 
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, t, ans, sz[maxn], dp[maxn];
pll a[maxn];
vector<pll> vec[maxn];
vector<ll> g[maxn];
bool vis[maxn];

void dfs(ll v){
	vis[v] = 1;
	dp[v] = sz[v];
	for(ll u : g[v]){
		if(!vis[u]){
			dfs(u);
			ans = (ans + dp[u] * (n - dp[u])) % mod;
			dp[v] += dp[u];
		}
	}
	return;
}

int DistanceSum(int _n, int *x, int *y){
	n = _n;
	ll mnx = inf;
	for(ll i = 0; i < n; i++){
		mnx = min(mnx, (ll)x[i]);
	}
	for(ll i = 0; i < n; i++){
		x[i] -= mnx;
	}
	ll mny = inf;
	for(ll i = 0; i < n; i++){
		mny = min(mny, (ll)y[i]);
	}
	for(ll i = 0; i < n; i++){
		y[i] -= mny;
	}
	for(ll i = 0; i < n; i++){
		vec[x[i]].pb(Mp(y[i], -1));
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i].empty()) break;
		sort(all(vec[i]));
		for(ll j = 0; j < Sz(vec[i]); j++){
			if(j && vec[i][j].F != vec[i][j - 1].F + 1) t++;
			sz[vec[i][j].S = t]++;
		}
		t++;
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i + 1].empty()) continue;
		ll p1 = 0, p2 = 0;
		while(p1 < Sz(vec[i]) && p2 < Sz(vec[i + 1])){
			if(vec[i][p1].F == vec[i + 1][p2].F){
				g[vec[i][p1].S].pb(vec[i + 1][p2].S);
				g[vec[i + 1][p2].S].pb(vec[i][p1].S);
			}
			if(vec[i][p1].F < vec[i + 1][p2].F) p1++;
			else p2++;
		}
	}
	dfs(0);
	t = 0;
	for(ll i = 0; i < maxn; i++){
		vis[i] = 0;
		sz[i] = 0;
		vec[i].clear();
		g[i].clear();
	}
	swap(x, y);
	for(ll i = 0; i < n; i++){
		vec[x[i]].pb(Mp(y[i], -1));
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i].empty()) break;
		sort(all(vec[i]));
		for(ll j = 0; j < Sz(vec[i]); j++){
			if(j && vec[i][j].F != vec[i][j - 1].F + 1) t++;
			sz[vec[i][j].S = t]++;
		}
		t++;
	}
	for(ll i = 0; i < maxn; i++){
		if(vec[i + 1].empty()) continue;
		ll p1 = 0, p2 = 0;
		while(p1 < Sz(vec[i]) && p2 < Sz(vec[i + 1])){
			if(vec[i][p1].F == vec[i + 1][p2].F){
				g[vec[i][p1].S].pb(vec[i + 1][p2].S);
				g[vec[i + 1][p2].S].pb(vec[i][p1].S);
			}
			if(vec[i][p1].F < vec[i + 1][p2].F) p1++;
			else p2++;
		}
	}
	dfs(0);
	return ans;
}

/*int main(){
    fast_io;
    
    int n, x[100], y[100];
    cin >> n;
    for(ll i = 0; i < n; i++){
    	cin >> x[i] >> y[i];
	}
	cout << DistanceSum(n, x, y);
 
    return 0;
}*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12908 KB Output is correct
2 Correct 18 ms 13548 KB Output is correct
3 Correct 30 ms 14444 KB Output is correct
4 Correct 30 ms 16108 KB Output is correct
5 Correct 48 ms 17772 KB Output is correct
6 Correct 51 ms 21356 KB Output is correct
7 Correct 51 ms 20460 KB Output is correct
8 Correct 50 ms 17772 KB Output is correct
9 Correct 52 ms 19564 KB Output is correct
10 Correct 61 ms 21792 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 13036 KB Output is correct
2 Correct 19 ms 13292 KB Output is correct
3 Correct 37 ms 15468 KB Output is correct
4 Correct 34 ms 15596 KB Output is correct
5 Correct 63 ms 19564 KB Output is correct
6 Correct 55 ms 19564 KB Output is correct
7 Correct 62 ms 18924 KB Output is correct
8 Correct 57 ms 19948 KB Output is correct
9 Correct 60 ms 18540 KB Output is correct
10 Correct 55 ms 19564 KB Output is correct