oj.uz

Submission #1013157

# Submission time Handle Problem Language Result Execution time Memory
1013157 2024-07-03T08:46:39 Z jcelin Ideal city (IOI12_city) C++14
100 / 100
 124 ms 23356 KB 
#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;

const int MAXN = 1e5 + 7;
const int logo = 17;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};

struct uf{
	int par[MAXN], sz[MAXN];
	
	void res(){
		for(int i=0; i<MAXN; i++) par[i] = i, sz[i] = 0;
	}
	
	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	
	bool unite(int a, int b){
		a = find(a), b = find(b);
		if(a == b) return 0;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
		return 1;
	}
}t;

unordered_map<ll, int> id, inp, ve;
ll ans;

ll vl(ll a, ll b){
	return a * MAXN + b;
}


vi g[MAXN];
int siz[MAXN], n;

void dfs(int u, int p = -1){
	for(auto &x : g[u]){
		if(x == p) continue;
		dfs(x, u);
		siz[u] += siz[x];
	}
	
	for(auto &x : g[u]){
		if(x == p) continue;
		//cout << u << " " << x << " " << n << " " << siz[x] << "\n";
		ans += (ll)siz[x] * (ll)(n - siz[x]);
	}
}

ll calc(int _n, int *x, int *y){
	//cout << "\n";
	n = _n;
	id.clear(), inp.clear(), ve.clear();
	for(int i=0; i<MAXN; i++) g[i].clear();
	t.res();
	ans = 0;
	
	vi a, b;
	for(int i=0; i<n; i++) a.PB(x[i]), b.PB(y[i]), t.sz[i] = 1;
	
	int mi = a[0], mj = b[0];
	for(auto &c : a) mi = min(mi, c);
	for(auto &c : b) mj = min(mj, c);
	for(auto &c : a) c -= mi;
	for(auto &c : b) c -= mj;
	
	for(int i=0; i<n; i++){
		id[vl(a[i], b[i])] = i;
		inp[vl(a[i], b[i])] = 1;
	}
	
	for(int i=0; i<n; i++){
		int cx = a[i] - 1, cy = b[i];
		ll j = vl(cx, cy);
		if(inp[j]){
			j = id[j];
			t.unite(i, j);
		}
	}
	
	for(int i=0; i<MAXN; i++) siz[i] = t.sz[i];
	
	for(int i=0; i<n; i++){
		int cx = a[i], cy = b[i] - 1;
		ll j = vl(cx, cy);
		if(!inp[j]) continue;
		j = id[j];
		
		int ni = t.find(i);
		int nj = t.find(j);
		ll cos = vl(ni, nj);
		ll cos2 = vl(nj, ni);
		if(ve[cos] == 0){
			ve[cos] = 1;
			ve[cos2] = 1;
			g[ni].PB(nj);
			g[nj].PB(ni);
		}
	}
	
	for(int i=0; i<MAXN; i++) if(t.find(i) == i and t.sz[i]){
		dfs(i);
		break;
	}
	return ans;
}

int DistanceSum(int _n, int *x, int *y){
	return ((ll)calc(_n, x, y) + (ll)calc(_n, y, x)) % mod;
}

/*
int xx[MAXN], yy[MAXN];
void solve(){
	int _n;
	cin >> _n;
	for(int i=0; i<_n; i++) cin >> xx[i] >> yy[i];
	cout << DistanceSum(_n, xx, yy) << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int _ = 1;
	//cin >> _;
	while(_--) solve();
	return 0;
}


*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 3 ms 4336 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 3 ms 4188 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 4 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6152 KB Output is correct
2 Correct 14 ms 6328 KB Output is correct
3 Correct 33 ms 9876 KB Output is correct
4 Correct 33 ms 9768 KB Output is correct
5 Correct 74 ms 15588 KB Output is correct
6 Correct 65 ms 15588 KB Output is correct
7 Correct 78 ms 16180 KB Output is correct
8 Correct 69 ms 15588 KB Output is correct
9 Correct 75 ms 16104 KB Output is correct
10 Correct 87 ms 21988 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7864 KB Output is correct
2 Correct 19 ms 7092 KB Output is correct
3 Correct 53 ms 13192 KB Output is correct
4 Correct 44 ms 12136 KB Output is correct
5 Correct 124 ms 22696 KB Output is correct
6 Correct 93 ms 18536 KB Output is correct
7 Correct 118 ms 23356 KB Output is correct
8 Correct 103 ms 18752 KB Output is correct
9 Correct 89 ms 18084 KB Output is correct
10 Correct 86 ms 17748 KB Output is correct