oj.uz

Submission #363119

# Submission time Handle Problem Language Result Execution time Memory
363119 2021-02-05T05:14:56 Z Kevin_Zhang_TW Ideal city (IOI12_city) C++17
100 / 100
 393 ms 20420 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, inf = 1e9;

int N;
vector<int> edge[MAX_N];
struct dsu {
	vector<int> g, sz;
	dsu(int n) {
		g.resize(n), sz.resize(n, 1), iota(AI(g), 0);
	}
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	bool M(int a, int b) {
		a = F(a), b = F(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		return sz[a] += sz[b], g[b] = a, true;
	}
	int S(int i) { return sz[F(i)]; }
	int operator()(int i) { return F(i); }
};

ll subsz[MAX_N];
ll dfs(int x, ll allsz, int lst = -1) {
	ll res = 0;
	for (int u : edge[x]) if (u != lst) {
		res += dfs(u, allsz, x);
		subsz[x] += subsz[u];
	}
	return res += subsz[x] * (allsz - subsz[x]);
}
ll cal(int N, int *X, int *Y) {
	dsu D(N);
	int sz = N;
	vector<pair<int,int>> alle;
	{
		map<int, vector<pair<int,int>>> col;
		for (int i = 0;i < N;++i)
			col[ X[i] ].pb( Y[i], i );
		for (auto &[_, vec] : col) {
			sort(AI(vec));
			for (int i = 1;i < vec.size();++i) {
				if (vec[i].first - vec[i-1].first == 1)
					sz -= D.M(vec[i].second, vec[i-1].second);
			}
		}
	}
	map<pair<int,int>, int> loc;
	auto update = [&](int id, int x, int y) {
		if (loc.count({x, y})) {
			int bid = loc[{x, y}];
			int a = D(id), b = D(bid);
			if (a > b) swap(a, b);
			alle.pb(a, b);
		}
	};
	for (int i = 0;i < N;++i) {
		int x = X[i], y = Y[i];
		update(i, x+1, y), update(i, x-1, y);
		loc[{x, y}] = i;
	}

	sort(AI(alle));
	alle.resize(unique(AI(alle)) - begin(alle));

	DE(alle.size(), sz);
	assert(alle.size() + 1 == sz);

	for (int i = 0;i < N;++i) {
		edge[i].clear();
		subsz[i] = D.S(i);
	}
	for (auto [a, b] : alle)
		edge[a].pb(b), edge[b].pb(a);

	return dfs(D(0), N);
}
int DistanceSum(int N, int *X, int *Y) {
	ll res = cal(N, X, Y) + cal(N, Y, X);
	return res % 1'000'000'000;
}

Compilation message

city.cpp: In function 'll cal(int, int*, int*)':
city.cpp:56:21: 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 = 1;i < vec.size();++i) {
      |                   ~~^~~~~~~~~~~~
city.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
city.cpp:80:2: note: in expansion of macro 'DE'
   80 |  DE(alle.size(), sz);
      |  ^~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from city.cpp:1:
city.cpp:81:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |  assert(alle.size() + 1 == sz);
      |         ~~~~~~~~~~~~~~~~^~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7532 KB Output is correct
2 Correct 7 ms 7532 KB Output is correct
3 Correct 8 ms 7532 KB Output is correct
4 Correct 8 ms 7532 KB Output is correct
5 Correct 9 ms 7660 KB Output is correct
6 Correct 9 ms 7660 KB Output is correct
7 Correct 9 ms 7660 KB Output is correct
8 Correct 9 ms 7660 KB Output is correct
9 Correct 9 ms 7532 KB Output is correct
10 Correct 9 ms 7532 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9420 KB Output is correct
2 Correct 59 ms 9448 KB Output is correct
3 Correct 159 ms 12260 KB Output is correct
4 Correct 140 ms 12260 KB Output is correct
5 Correct 362 ms 16920 KB Output is correct
6 Correct 351 ms 17124 KB Output is correct
7 Correct 366 ms 17088 KB Output is correct
8 Correct 336 ms 16964 KB Output is correct
9 Correct 363 ms 17372 KB Output is correct
10 Correct 308 ms 20420 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 9740 KB Output is correct
2 Correct 52 ms 9716 KB Output is correct
3 Correct 146 ms 13164 KB Output is correct
4 Correct 139 ms 12900 KB Output is correct
5 Correct 378 ms 18912 KB Output is correct
6 Correct 335 ms 17960 KB Output is correct
7 Correct 371 ms 18924 KB Output is correct
8 Correct 348 ms 17900 KB Output is correct
9 Correct 393 ms 17568 KB Output is correct
10 Correct 336 ms 17384 KB Output is correct