oj.uz

Submission #382826

# Submission time Handle Problem Language Result Execution time Memory
382826 2021-03-28T09:25:15 Z alishahali1382 Ideal city (IOI12_city) C++14
100 / 100
 78 ms 14188 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll ans;
int n, m, k, u, v, x, y, t, a, b;
int par[MAXN], sz[MAXN];
vector<pii> v1[MAXN], v2[MAXN];
vector<int> G[MAXN];

int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
void join(int x, int y){
//	debug2(x, y)
	x=get(x);
	y=get(y);
	if (x==y) return ;
	if (x<y) swap(x, y);
	par[x]=y;
	sz[y]+=sz[x];
}
int dfs(int node, int par){
//	debug2(node, sz[node])
	for (int v:G[node]) if (v!=par) sz[node]+=dfs(v, node);
//	debug2(node, sz[node])
	ans+=1ll*sz[node]*(n-sz[node]);
	return sz[node];
}
void Solve(){
	for (int i=0; i<MAXN; i++) for (int j=1; j<SZ(v1[i]); j++)
		if (v1[i][j].first-v1[i][j-1].first==1) join(v1[i][j].second, v1[i][j-1].second);
	for (int i=1; i<MAXN; i++){
		int j=0;
		for (int jj=0; jj<SZ(v1[i-1]); jj++){
			pii p=v1[i-1][jj];
			while (j<SZ(v1[i]) && p.first>v1[i][j].first) j++;
			if (j<SZ(v1[i]) && p.first==v1[i][j].first){
				if (jj && j && v1[i-1][jj-1].first==v1[i][j-1].first && v1[i-1][jj-1].first==p.first-1) continue ;
//				debug2(p.second, v1[i][j].second)
				G[get(p.second)].pb(get(v1[i][j].second));
				G[get(v1[i][j].second)].pb(get(p.second));
			}
		}
	}
	dfs(0, 0);
}

int DistanceSum(int nn, int *X, int *Y){
	n=nn;
	x=*min_element(X, X+n);
	y=*min_element(Y, Y+n);
	for (int i=0; i<n; i++){
		X[i]-=x;
		Y[i]-=y;
		// :)
		v1[X[i]].pb({Y[i], i});
		v2[Y[i]].pb({X[i], i});
		par[i]=i;
		sz[i]=1;
	}
	for (int i=0; i<MAXN; i++){
		sort(all(v1[i]));
		sort(all(v2[i]));
	}
	Solve();
//	debug(ans)	
	
	for (int i=0; i<MAXN; i++) v1[i].swap(v2[i]);
	for (int i=0; i<n; i++){
		swap(X[i], Y[i]);
		par[i]=i;
		sz[i]=1;
		G[i].clear();
	}
	Solve();
//	debug(ans)
	return ans%1000000000;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8300 KB Output is correct
2 Correct 15 ms 8300 KB Output is correct
3 Correct 27 ms 9452 KB Output is correct
4 Correct 27 ms 9324 KB Output is correct
5 Correct 49 ms 12012 KB Output is correct
6 Correct 48 ms 11648 KB Output is correct
7 Correct 49 ms 11628 KB Output is correct
8 Correct 48 ms 11884 KB Output is correct
9 Correct 49 ms 11372 KB Output is correct
10 Correct 60 ms 14172 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8684 KB Output is correct
2 Correct 17 ms 8684 KB Output is correct
3 Correct 43 ms 10732 KB Output is correct
4 Correct 34 ms 10476 KB Output is correct
5 Correct 78 ms 14188 KB Output is correct
6 Correct 57 ms 13036 KB Output is correct
7 Correct 73 ms 14188 KB Output is correct
8 Correct 58 ms 13036 KB Output is correct
9 Correct 57 ms 12780 KB Output is correct
10 Correct 54 ms 12652 KB Output is correct