oj.uz

Submission #316928

# Submission time Handle Problem Language Result Execution time Memory
316928 2020-10-28T15:38:44 Z tengiz05 Ideal city (IOI12_city) C++17
55 / 100
 143 ms 19960 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+5, mod = 1e9;
ll x[N], y[N], n;
ll d1[4] = {0, 0, 1, -1};
ll d2[4] = {1,-1, 0,  0};
vector<int> edges[N];
int DistanceSum(int NN, int *X, int *Y) {
	n = NN;
	map<pair<int, int>, bool> used, m, road;
	map<pair<int, int>, int> r;
	for(int i=0;i<n;i++){
		x[i] = X[i], y[i] = Y[i];
		m[{x[i], y[i]}] = true;
		r[{x[i], y[i]}] = i;
	}
	ll ans = 0;
	if(n <= 3000){
	queue<tuple<int, int, int>> Q;
	Q.push(make_tuple(x[0], y[0], 0));
	used[{x[0], y[0]}] = true;
	while(!Q.empty()){
		auto P = Q.front();Q.pop();
		int f, s, node;
		tie(f, s, node) = P;
		for(int i=0;i<4;i++){
			int nf = f+d1[i], ns = s+d2[i];
			if(!m[{nf, ns}])continue;
			if(!road[{node, r[{nf, ns}]}]){
				edges[node].push_back(r[{nf,ns}]);
				edges[r[{nf,ns}]].push_back(node);
				road[{node, r[{nf, ns}]}] = true;
				road[{r[{nf, ns}], node}] = true;
			}else continue;
			if(!used[{nf, ns}]){
				Q.push(make_tuple(nf, ns, r[{nf, ns}]));
			}used[{nf, ns}] = true;
		}
	}
//	for(int i=0;i<n;i++){cout << i << ":   ";for(auto x : edges[i])cout << x << ' ';cout << '\n';}cout << "\n\n";
		for(int p=0;p<n;p++){
			queue<int> q;
			q.push(p);
			vector<int> dist(n, mod*2);dist[p] = 0;
			while(!q.empty()){
				int u=q.front();q.pop();
				for(auto v : edges[u]){
					if(dist[u]+1 < dist[v]){
						dist[v] = dist[u]+1;
						q.push(v);
					}
				}
			}for(int i=p+1;i<n;i++)ans += dist[i], ans %= mod;
		}
	}else {
		sort(x, x+n);
		sort(y, y+n);
		vector<ll> sx(n+1), sy(n+1);
		for(int i=n-1;i>=0;i--){
			sx[i] = sx[i+1]+x[i];
			sy[i] = sy[i+1]+y[i];
		}for(int i=0;i<n-1;i++){
			ll t = x[i]*(n-i-1);
			ans += (sx[i+1]-t)%mod;ans %= mod;
			t = y[i]*(n-i-1);
			ans += (sy[i+1]-t)%mod;ans %= mod;
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3072 KB Output is correct
2 Correct 37 ms 3200 KB Output is correct
3 Correct 74 ms 3448 KB Output is correct
4 Correct 76 ms 3328 KB Output is correct
5 Correct 126 ms 3708 KB Output is correct
6 Correct 125 ms 3704 KB Output is correct
7 Correct 127 ms 3704 KB Output is correct
8 Correct 126 ms 3704 KB Output is correct
9 Correct 122 ms 3704 KB Output is correct
10 Correct 129 ms 3584 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6016 KB Output is correct
2 Correct 24 ms 6052 KB Output is correct
3 Correct 62 ms 11000 KB Output is correct
4 Correct 60 ms 11000 KB Output is correct
5 Correct 134 ms 19192 KB Output is correct
6 Correct 138 ms 19168 KB Output is correct
7 Correct 139 ms 19192 KB Output is correct
8 Correct 137 ms 19192 KB Output is correct
9 Correct 142 ms 19832 KB Output is correct
10 Correct 143 ms 19960 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 6016 KB Output isn't correct
2 Halted 0 ms 0 KB -