Submission #987783

#	Time	Username	Problem	Language	Result	Execution time	Memory
987783		vjudge1	Ideal city (IOI12_city)	C++17	100 / 100	66 ms	14776 KiB

city

#pragma GCC optimize("Ofast,O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define X [0]
#define Y [1]
using namespace std;

const int MX = 1e5+5, MOD = 1'000'000'000,
	DX[] = {0,0,1,-1}, DY[] = {1,-1,0,0};
	
const ll INF = 1e15;


int n;
vector<vector<array<int, 2>>> nodes;
vector<array<int, 2>> a;

/*
1- Build nodes for each horizontal level (each node has an index)
2- Build edges by keeping a pointer
3- DP on trees, sum of all pairs
*/

vector<int> adj[MX];
ll cnt[MX], subdist[MX], dist[MX];
 map<int, array<int, 2>> nodemp;
 
void dfs(int node = 0, int par = -1)
{
	auto vv = nodemp[node];
	auto rng = nodes[vv X][vv Y];
	cnt[node] = rng Y - rng X + 1;
	for (int ch : adj[node])
		if (ch ^ par) {
			dfs(ch, node);
			cnt[node] += cnt[ch];
			subdist[node] += subdist[ch] + cnt[ch];
		}
}
 
void dfs2(int node = 0, int par = -1)
{
	for (int ch : adj[node])
		if (ch ^ par) {
			dist[ch] = (dist[node] - subdist[ch] - cnt[ch]) + (n - cnt[ch]);
			dfs2(ch, node);
		}
}

int solve()
{
	nodes.clear();
	sort(a.begin(), a.end());
	const int lvlcnt = a.back()[0] - a.front()[0] + 1;
	//cout << "===\n";
//	cout << lvlcnt;
	/*
	for (int i = 0; i < n; i++)
		cout << a[i][0] << ' ' << a[i][1] << '\n';
	*/
	nodes.resize(a.back()[0] - a.front()[0] + 1);
	int px = -1, py = -1;
	int idx = 0;
	for (int i = 0; i < n; i++) {
		if (px == a[i]X && py == a[i]Y-1) {
			nodes[a[i]X].back()Y = a[i]Y;
		}
		else {
			nodes[a[i]X].push_back({a[i]Y, a[i]Y});
			idx++;
		}
		px = a[i]X, py = a[i]Y;
	}
	
	
	int pref = 0;

	nodemp.clear();
	for (int j = 0; j < nodes[0].size(); j++)
		nodemp[j] = {0, j};
	for (int i = 0; i < MX; i++)
		i[adj].clear();
	
	for (int i = 1; i < lvlcnt; i++) {
		int pnt = 0;
		for (int j = 0; j < nodes[i].size(); j++) {
			nodemp[pref + nodes[i-1].size() + j] = {i, j};
			
			if (pnt > 0) pnt --;
			while (pnt < nodes[i-1].size() && nodes[i-1][pnt]Y < nodes[i][j]X)
				pnt++;
			while (pnt < nodes[i-1].size() && (nodes[i-1][pnt]X <= nodes[i][j]Y || nodes[i-1][pnt]Y <= nodes[i][j]Y)) {
				adj[pref + nodes[i-1].size() + j].push_back(pref + pnt);
				adj[pref + pnt].push_back(pref + nodes[i-1].size() + j);
				pnt++;	
			}
		}
		pref += nodes[i-1].size();
	}
	pref += nodes[lvlcnt-1].size();
	
	
	// for (int i = 0; i < pref; i++) {
		// cout << i << ": ";
		// for (int j : adj[i])
			// cout << j << ' ';
		// cout << '\n';
	// }
		
	
	// DP on trees
	
	memset(dist, 0, sizeof dist);
	memset(cnt, 0, sizeof cnt);
	memset(subdist, 0, sizeof subdist);
	
	ll sum = 0;
	
	dfs();
	dist[0] = subdist[0];
	dfs2();
	for (int i = 0; i < pref; i++) {
		auto [w, e] = nodemp[i];
		//cout << i << "# " << w << ": " << nodes[w][e]X << ' ' << nodes[w][e]Y << " " << n << " " << cnt[i]<<'\n';
		sum += (cnt[i]) * (n - cnt[i]); //dist[i];
		sum %= MOD;
		idx++;
	}
	
	return sum;
}

int DistanceSum(int n_, int x[], int y[]) {
	n = n_;
	a.reserve(n);
	for (int i = 0; i < n; i++)
		a.push_back({x[i], y[i]});
	int mnx = *min_element(x, x+n), mny = *min_element(y, y+n);
	
	for (int i = 0; i < n; i++)
		a[i]X -= mnx, a[i]Y -= mny;
	int h = solve();
	for (int i = 0; i < n; i++)
		swap(a[i][0], a[i][1]);
	
	int v = solve();
	//cout << "#: " << h << " " << v << '\n';
	return (h+v)%MOD;
}


#ifdef MUAATH_5

int main() {
  int tmp;
  int N, i;
  tmp = scanf("%d", &N);
  assert(tmp == 1);
  int *sq_x, *sq_y;
  sq_x = (int*) malloc(N * sizeof(int));
  sq_y = (int*) malloc(N * sizeof(int));
  for (i = 0; i < N; i++) {
    tmp = scanf("%d %d", &sq_x[i], &sq_y[i]);
    //assert(tmp == 2);
  }
  int ds = DistanceSum(N, sq_x, sq_y);
  printf("%d\n", ds);

}
#endif

Compilation message (stderr)

city.cpp: In function 'int solve()':
city.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int j = 0; j < nodes[0].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~
city.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int j = 0; j < nodes[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
city.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    while (pnt < nodes[i-1].size() && nodes[i-1][pnt]Y < nodes[i][j]X)
      |           ~~~~^~~~~~~~~~~~~~~~~~~
city.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    while (pnt < nodes[i-1].size() && (nodes[i-1][pnt]X <= nodes[i][j]Y || nodes[i-1][pnt]Y <= nodes[i][j]Y)) {
      |           ~~~~^~~~~~~~~~~~~~~~~~~
city.cpp:124:8: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  124 |   auto [w, e] = nodemp[i];
      |        ^~~~~~

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