Submission #780833

#	Time	Username	Problem	Language	Result	Execution time	Memory
780833		NothingXD	Ideal city (IOI12_city)	C++17	100 / 100	507 ms	15716 KiB

city

#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 (stderr)

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