Submission #1153442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153442		sano	Ideal city (IOI12_city)	C++20	100 / 100	100 ms	18872 KiB

city

//#include "crocodile.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

vec<vec<ll>> g;
vec<ll> pod;
ll vys = 0;
ll suc = 0;

ll dfs(ll x, ll pr) {
	for (auto i : g[x]) {
		if (i == pr) continue;
		ll dd = dfs(i, x);
		pod[x] += dd;
		vys += dd * (suc - dd);
		
	}
	return pod[x];
}


void horizontalne(ll n, vec<pii> a) {
	sort(a.begin(), a.end());
	map<pii, ll> umap;
	ll poc = 0;
	pii pos = { -1, -1 };
	vec<ll> vel(n, 0);
	map<pii, bool> h;
	For(i, n) {
		if (pos.ff != a[i].ff || pos.ss != (a[i].ss - 1)) {
			poc++;
		}
		vel[poc]++;
		if (umap.find({ a[i].ff - 1, a[i].ss }) != umap.end()) {
			h[{ poc, umap[{ a[i].ff - 1, a[i].ss  }] }] = 1;
		}
		umap[a[i]] = poc;
		pos = a[i];
	}
	g.resize(n);
	pod.resize(n, 0);
	For(i, n) {
		pod[i] = vel[i];
		suc += vel[i];
	}
	for (auto i : h) {
		g[i.ff.ff].push_back(i.ff.ss);
		g[i.ff.ss].push_back(i.ff.ff);
	}
	dfs(1, -1);
	suc = 0;
	pod.clear();
	g.clear();
	return;
}

void vertikalne(ll n, vec<pii> a) {
	For(i, a.size()) {
		swap(a[i].ff, a[i].ss);
	}
	sort(a.begin(), a.end());
	map<pii, ll> umap;
	ll poc = 0;
	pii pos = { -1, -1 };
	vec<ll> vel(n, 0);
	map<pii, bool> h;
	For(i, n) {
		if (pos.ff != a[i].ff || pos.ss != (a[i].ss - 1)) {
			poc++;
		}
		vel[poc]++;
		if (umap.find({ a[i].ff - 1, a[i].ss }) != umap.end()) {
			h[{ poc, umap[{ a[i].ff - 1, a[i].ss  }] }] = 1;
		}
		umap[a[i]] = poc;
		pos = a[i];
	}
	g.resize(n);
	pod.resize(n, 0);
	For(i, n) {
		pod[i] = vel[i];
		suc += vel[i];
	}
	for (auto i : h) {
		g[i.ff.ff].push_back(i.ff.ss);
		g[i.ff.ss].push_back(i.ff.ff);
	}
	dfs(1, -1);
	suc = 0;
	pod.clear();
	g.clear();
	return;
}


ll DistanceSum(int n1, int x[], int y[]) {
	ll n = n1;
	vec<pii> a;
	For(i, n) a.push_back({ x[i], y[i] });
	horizontalne(n, a);
	vertikalne(n, a);
	return (vys % 1000000000);
}


/*signed main() {
	//ll t; cin >> t;
	ll t = 1;
	For(w, t){
		ll n;
		cin >> n;
		ll x[100], y[100];
		For(i, n) {
			cin >> x[i] >> y[i];
		}
		DistanceSum(n, x, y);
	}
	return 0;
}*/

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45