oj.uz

답안 #587386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587386 2022-07-01T18:24:43 Z GioChkhaidze 이상적인 도시 (IOI12_city) C++14
100 / 100
 347 ms 20800 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second

using namespace std;

const int Nn = 1e5 + 5;

ll tot[Nn], ans, mod = 1e9;
int n, id[Nn], x[Nn], y[Nn], c[Nn];
int a[4] = {1, -1, 0, 0};
int b[4] = {0, 0, 1, -1};
map < pair < int , int > , int > f;
vector < int > v[Nn];

void dfs(int x, int p) {
	tot[x] = c[x];
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to == p) continue;
		dfs(to, x);
		tot[x] += tot[to];
	}
	ans += (tot[x] * (n - tot[x])) % mod;
	ans %= mod;
}

void solve() {
	vector < pair < pair < int , int > , int > > s;
	for (int i = 0; i < n; ++i) {
		f[{x[i], y[i]}] = i;
		s.pb({{x[i], y[i]}, i});
	}
	sort(s.begin(), s.end());
	int nd = 0;
	for (int i = 0; i < s.size(); ++i) {
		if (!i || (s[i - 1].f.f != s[i].f.f || s[i - 1].f.s + 1 < s[i].f.s)) ++nd;
		id[s[i].s] = nd, ++c[nd];
	}
	vector < pair < int , int > > ss;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			int Ax = x[i] + a[j], Ay = y[i] + b[j]; 
			if (f.find({Ax, Ay}) != f.end()) {
				int A = id[i];
				int B = id[f[{Ax, Ay}]];
				if (A > B) swap(A, B);
				ss.pb({A, B});
			}
		}
	}
	sort(ss.begin(), ss.end());
	for (int i = 0; i < ss.size(); ++i) {
		if (!i || ss[i - 1] != ss[i]) {
			v[ss[i].f].pb(ss[i].s);
			v[ss[i].s].pb(ss[i].f);
		}
	}
	dfs(1, 1);
}

void clear() {
	f.clear();
	for (int i = 1; i <= n; ++i) {
		v[i].clear(), c[i] = tot[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		swap(x[i], y[i]);
	}
}

int DistanceSum(int nn, int *X, int *Y) {
	n = nn;
	for (int i = 0; i < n; ++i) {
		x[i] = X[i], y[i] = Y[i];
	}
	solve();
	clear();
	solve();
	return ans;
}

Compilation message

city.cpp: In function 'void dfs(int, int)':
city.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
city.cpp: In function 'void solve()':
city.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
city.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < ss.size(); ++i) {
      |                  ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 4 ms 2900 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 5 ms 2884 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 5 ms 2964 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 5 ms 2956 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 5644 KB Output is correct
2 Correct 45 ms 5848 KB Output is correct
3 Correct 127 ms 10308 KB Output is correct
4 Correct 129 ms 10400 KB Output is correct
5 Correct 301 ms 17740 KB Output is correct
6 Correct 329 ms 18136 KB Output is correct
7 Correct 347 ms 18212 KB Output is correct
8 Correct 321 ms 17904 KB Output is correct
9 Correct 303 ms 18152 KB Output is correct
10 Correct 254 ms 20800 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 5532 KB Output is correct
2 Correct 48 ms 5756 KB Output is correct
3 Correct 120 ms 10144 KB Output is correct
4 Correct 124 ms 10624 KB Output is correct
5 Correct 280 ms 17608 KB Output is correct
6 Correct 321 ms 18476 KB Output is correct
7 Correct 278 ms 17772 KB Output is correct
8 Correct 308 ms 18240 KB Output is correct
9 Correct 301 ms 18024 KB Output is correct
10 Correct 302 ms 17916 KB Output is correct