oj.uz

Submission #780833

# Submission time Handle Problem Language Result Execution time Memory
780833 2023-07-12T13:39:53 Z NothingXD Ideal city (IOI12_city) C++17
100 / 100
 507 ms 15716 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;
const int inf = 2147483647;
const int mod = 1e9;

int add(int x, int y){
	int res = x + y;
	if (res >= mod) return res - mod;
	if (res < 0) return res + mod;
	return res;
}

int n, ans, x[maxn], y[maxn], sz[maxn];
vector<int> valx[maxn], valy[maxn];
vector<int> g[maxn];

void dfs(int v, int p = -1){
	//debug(v);
	for (auto u: g[v]){
		if (u != p){
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	ans = add(ans, 1ll * sz[v] * (n-sz[v]) % mod);
	//debug(v, sz[v]);
}

int DistanceSum(int N, int *X, int *Y) {

	n = N;
	int mnx = inf, mny = inf, mx = 0, my = 0;
	for (int i = 1; i <= n; i++){
		x[i] = X[i-1];
		y[i] = Y[i-1];
		mnx = min(mnx, x[i]);
		mny = min(mny, y[i]);
	}
	mnx--;
	mny--;
	for (int i = 1; i <= n; i++){
		x[i] -= mnx;
		y[i] -= mny;
		valx[x[i]].push_back(y[i]);
		valy[y[i]].push_back(x[i]);
		mx = max(mx, x[i]);
		my = max(my, y[i]);
		cerr << x[i] << ' ' << y[i] << endl;
	}
	int cnt = 0;
	vector<pair<int,pii>> ver;
	for (int i = 1; i <= mx; i++){
		vector<pair<int,pii>> tmp;
		sort(all(valx[i]));
		int l = valx[i][0];
		for (int j = 1; j < valx[i].size(); j++){
			if (valx[i][j] != valx[i][j-1] + 1){
				cnt++;
				tmp.push_back({cnt, {l, valx[i][j-1]}});
				//debug(i, cnt, l, valx[i][j-1]);
				sz[cnt] = valx[i][j-1] - l + 1;
				l = valx[i][j];
			}
		}
		cnt++;
		tmp.push_back({cnt, {l, valx[i].back()}});
		//debug(i, cnt, l, valx[i].back());
		sz[cnt] = valx[i].back() - l + 1;
		int ptr = 0;
		for (auto [x, y]: tmp){
			while(ptr < ver.size() && ver[ptr].S.S <= y.S){
				if (y.F <= ver[ptr].S.S){
				//	debug(ver[ptr].F, x);
					g[ver[ptr].F].push_back(x);
					g[x].push_back(ver[ptr].F);
				}
				ptr++;
			}
			if (ptr != ver.size() && ver[ptr].S.F <= y.S){
			//	debug(ver[ptr].F, x);
				g[ver[ptr].F].push_back(x);
				g[x].push_back(ver[ptr].F);
			}
		}
		ver = tmp;
	}
	dfs(1);
	for (int i = 1; i <= cnt; i++){
		g[i].clear();
	}
	memset(sz, 0, sizeof sz);
	ver.clear();
	cnt = 0;

	for (int i = 1; i <= my; i++){
		vector<pair<int,pii>> tmp;
		sort(all(valy[i]));
		int l = valy[i][0];
		for (int j = 1; j < valy[i].size(); j++){
			if (valy[i][j] != valy[i][j-1] + 1){
				cnt++;
			//	debug(i, cnt, l, valy[i][j-1]);
				tmp.push_back({cnt, {l, valy[i][j-1]}});
				sz[cnt] = valy[i][j-1] - l + 1;
				l = valy[i][j];
			}
		}
		cnt++;
		tmp.push_back({cnt, {l, valy[i].back()}});
		//debug(i, cnt, l, valy[i].back());
		sz[cnt] = valy[i].back() - l + 1;
		int ptr = 0;
		for (auto [x, y]: tmp){
			while(ptr < ver.size() && ver[ptr].S.S <= y.S){
				if (y.F <= ver[ptr].S.S){
				//	debug(ver[ptr].F, x);
					g[ver[ptr].F].push_back(x);
					g[x].push_back(ver[ptr].F);
				}
				ptr++;
			}
			if (ptr != ver.size() && ver[ptr].S.F <= y.S){
			//	debug(ver[ptr].F, x);
				g[ver[ptr].F].push_back(x);
				g[x].push_back(ver[ptr].F);
			}
		}
		ver = tmp;
	}
	dfs(1);
	return ans;
}

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int j = 1; j < valx[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
city.cpp:94:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    while(ptr < ver.size() && ver[ptr].S.S <= y.S){
      |          ~~~~^~~~~~~~~~~~
city.cpp:102:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    if (ptr != ver.size() && ver[ptr].S.F <= y.S){
      |        ~~~~^~~~~~~~~~~~~
city.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int j = 1; j < valy[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
city.cpp:137:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    while(ptr < ver.size() && ver[ptr].S.S <= y.S){
      |          ~~~~^~~~~~~~~~~~
city.cpp:145:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    if (ptr != ver.size() && ver[ptr].S.F <= y.S){
      |        ~~~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7812 KB Output is correct
2 Correct 8 ms 7792 KB Output is correct
3 Correct 10 ms 7820 KB Output is correct
4 Correct 10 ms 7764 KB Output is correct
5 Correct 13 ms 7828 KB Output is correct
6 Correct 12 ms 7840 KB Output is correct
7 Correct 13 ms 7764 KB Output is correct
8 Correct 16 ms 7764 KB Output is correct
9 Correct 12 ms 7820 KB Output is correct
10 Correct 12 ms 7752 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 8696 KB Output is correct
2 Correct 89 ms 8600 KB Output is correct
3 Correct 247 ms 9928 KB Output is correct
4 Correct 221 ms 9904 KB Output is correct
5 Correct 426 ms 12464 KB Output is correct
6 Correct 437 ms 12268 KB Output is correct
7 Correct 431 ms 12452 KB Output is correct
8 Correct 445 ms 12264 KB Output is correct
9 Correct 432 ms 12148 KB Output is correct
10 Correct 448 ms 15716 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8908 KB Output is correct
2 Correct 90 ms 8872 KB Output is correct
3 Correct 235 ms 10620 KB Output is correct
4 Correct 223 ms 10520 KB Output is correct
5 Correct 439 ms 13568 KB Output is correct
6 Correct 458 ms 12872 KB Output is correct
7 Correct 507 ms 13644 KB Output is correct
8 Correct 442 ms 12748 KB Output is correct
9 Correct 438 ms 12428 KB Output is correct
10 Correct 446 ms 12352 KB Output is correct