oj.uz

Submission #318028

# Submission time Handle Problem Language Result Execution time Memory
318028 2020-10-31T09:08:27 Z tengiz05 Ideal city (IOI12_city) C++17
100 / 100
 77 ms 11484 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long ll;
const ll N = 1e5+5, mod = 1e9;
ll sz[N], c[N], n, id[N];
bool used[N];
vector<int> edges[N];
vector<pair<int, int>> p;
ll ans;
void dfs(int u){
	sz[u] = c[u];
	used[u]=true;
	for(auto v : edges[u]){
		if(!used[v]){
			dfs(v);
			sz[u] += sz[v];
		}
	}ans += sz[u]*(n-sz[u]);ans%=mod;
}
void build(){
	sort(all(p));
	int timer=0;
	for(int i=0;i<n;i++){
		int e=i;
		while(e+1<n && p[e].ff == p[e+1].ff && p[e+1].ss == p[e].ss+1)e++;
		for(int j=i;j<=e;j++){
			int x = lower_bound(all(p), make_pair(p[j].ff-1, p[j].ss))-p.begin();
			if(p[x] == make_pair(p[j].ff-1, p[j].ss)){
				edges[id[x]].push_back(timer);
				edges[timer].push_back(id[x]);
			}id[j] = timer;
		}c[timer] = e-i+1;
		timer++;
		i = e;
	}dfs(0);
	for(int i=0;i<n;i++)c[i]=0, sz[i]=0, id[i]=0;
	for(int i=0;i<=timer;i++)edges[i].clear(), used[i]=0;
}
int DistanceSum(int NN, int *X, int *Y) {
	n = NN;
	for(int i=0;i<n;i++){
		p.push_back({X[i], Y[i]});
	}build();	
	p.clear();
	for(int i=0;i<n;i++){
		p.push_back({Y[i], X[i]});
	}build();
	return (int)ans%mod;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3976 KB Output is correct
2 Correct 15 ms 4200 KB Output is correct
3 Correct 35 ms 5732 KB Output is correct
4 Correct 32 ms 6160 KB Output is correct
5 Correct 62 ms 8800 KB Output is correct
6 Correct 62 ms 9568 KB Output is correct
7 Correct 63 ms 9568 KB Output is correct
8 Correct 62 ms 8672 KB Output is correct
9 Correct 67 ms 9320 KB Output is correct
10 Correct 64 ms 11484 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4072 KB Output is correct
2 Correct 15 ms 4200 KB Output is correct
3 Correct 37 ms 5988 KB Output is correct
4 Correct 36 ms 6120 KB Output is correct
5 Correct 77 ms 9312 KB Output is correct
6 Correct 71 ms 9436 KB Output is correct
7 Correct 77 ms 9464 KB Output is correct
8 Correct 70 ms 9312 KB Output is correct
9 Correct 70 ms 9056 KB Output is correct
10 Correct 68 ms 9184 KB Output is correct