oj.uz

Submission #99919

# Submission time Handle Problem Language Result Execution time Memory
99919 2019-03-08T18:08:01 Z jhnah917 Ideal city (IOI12_city) C++14
100 / 100
 281 ms 23672 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

const int mod = 1e9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int size[101010];
int  chk[101010];
int n;
map<p, int> mp;
set<int> g[101010];

void dfs(int now, int prv, ll &dist){
	for(auto nxt : g[now]){
		if(nxt ^ prv && !chk[nxt]){
			chk[nxt] = 1;
			dfs(nxt, now, dist);
			size[now] += size[nxt];
		}
	}
	ll tmp = (ll)size[now] * (ll)(n - size[now]);
	tmp %= mod;
	dist += tmp; dist %= mod;
}

ll getDist(){
	ll ret = 0;
	chk[1] = 1;
	dfs(1, 0, ret);
	return ret;
}

void makeTree(vector<p> &v){
	sort(v.begin()+1, v.end());
	memset(size, 0, sizeof size);
	memset(chk, 0, sizeof chk);
	for(int i=0; i<=n; i++) g[i].clear();
	mp.clear();
	
	int cnt = 1;
	mp[v[1]] = cnt;
	size[cnt]++;
	for(int i=2; i<=n; i++){
		if(v[i-1].x == v[i].x && v[i-1].y+1 == v[i].y){
			mp[v[i]] = cnt;
		}
		else mp[v[i]] = ++cnt;
		size[cnt]++;
	}
	
	for(int i=1; i<=n; i++){
		int x = v[i].x, y = v[i].y;
		int now = mp[v[i]];
		for(int k=0; k<4; k++){
			int xx = x + dx[k];
			int yy = y + dy[k];
			int nxt = mp[{xx, yy}];
			if(nxt && now != nxt) g[now].insert(nxt);
		}
	}
}

int DistanceSum(int N, int *X, int *Y){
	n = N;
	ll ret = 0;
	vector<p> v(n+1);
	for(int i=0; i<n; i++){
		v[i+1] = {X[i], Y[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	
	for(int i=0; i<n; i++){
		v[i+1] = {Y[i], X[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	ret %= mod;
	return (int)ret;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7660 KB Output is correct
2 Correct 40 ms 7652 KB Output is correct
3 Correct 109 ms 9936 KB Output is correct
4 Correct 104 ms 10264 KB Output is correct
5 Correct 213 ms 14004 KB Output is correct
6 Correct 211 ms 14200 KB Output is correct
7 Correct 223 ms 14612 KB Output is correct
8 Correct 213 ms 13956 KB Output is correct
9 Correct 206 ms 14776 KB Output is correct
10 Correct 241 ms 23160 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9464 KB Output is correct
2 Correct 45 ms 8696 KB Output is correct
3 Correct 141 ms 14712 KB Output is correct
4 Correct 125 ms 12792 KB Output is correct
5 Correct 281 ms 23164 KB Output is correct
6 Correct 262 ms 17656 KB Output is correct
7 Correct 272 ms 23672 KB Output is correct
8 Correct 230 ms 17912 KB Output is correct
9 Correct 220 ms 16632 KB Output is correct
10 Correct 225 ms 16408 KB Output is correct