Submission #316928

#	Time	Username	Problem	Language	Result	Execution time	Memory
316928		tengiz05	Ideal city (IOI12_city)	C++17	55 / 100	143 ms	19960 KiB

city

#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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45