oj.uz

Submission #776788

# Submission time Handle Problem Language Result Execution time Memory
776788 2023-07-08T09:27:12 Z ymm Collapse (JOI18_collapse) C++17
30 / 100
 1202 ms 23200 KB 
#include "collapse.h"

#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 100'010;

namespace dsu {
	int par[N];
	int sz[N];
	vector<pii> his;
	int cnt;
	bool rec;

	void init() {
		fill(par, par+N, -1);
		fill(sz, sz+N, 1);
		his.clear();
		cnt = 0;
		rec = 0;
	}

	int rt(int v) { return par[v] == -1? v: rt(par[v]); }

	void unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return;
		if (sz[v] < sz[u])
			swap(v, u);
		par[u] = v;
		sz[v] += sz[u];
		++cnt;
		if (rec)
			his.emplace_back(v, u);
	}

	void rollback() {
		while (his.size()) {
			auto [v, u] = his.back();
			his.pop_back();
			--cnt;
			sz[v] -= sz[u];
			par[u] = -1;
		}
		rec = 0;
	}
}

vector<pair<int,pii>> A[N], T[N];

void make_graph(vector<int> t, vector<int> V, vector<int> U)
{
	set<pair<pii,int>> e;
	Loop (i,0,t.size()) {
		int v = V[i], u = U[i];
		if (v > u)
			swap(v, u);
		if (t[i]) {
			auto it = e.lower_bound({{v, u}, -1});
			int l = it->second, r = i;
			A[v].push_back({u, {l,r}});
			T[u].push_back({v, {l,r}});
			e.erase(it);
		} else {
			e.insert({{v, u}, i});
		}
	}
	for (auto [dard, l] : e) {
		auto [v, u] = dard;
		int r = t.size();
		A[v].push_back({u, {l,r}});
		T[u].push_back({v, {l,r}});
	}
}

const int S = 1000;
int ans[N];

std::vector<int> simulateCollapse(
	int n,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	make_graph(T, X, Y);
	vector<int> Q(W.size());
	iota(Q.begin(), Q.end(), 0);
	sort(Q.begin(), Q.end(), [&](int i, int j) { return W[i] < W[j]; });
	for (int l = 0, r = 0; l < W.size(); l = r) {
		while (r < W.size() && W[Q[r]] - W[Q[l]] <= S)
			++r;
		vector<int> Q2;
		Loop (i,l,r)
			Q2.push_back(Q[i]);
		sort(Q2.begin(), Q2.end(), [&](int i, int j) { return P[i] < P[j]; });
		Loop (phase,0,2) {
			dsu::init();
			vector<pair<pii,pii>> E;
			int p = phase == 0? 0: n-1;
			for (int q : Q2) {
				while (phase == 0? p <= P[q]: p > P[q]) {
					for (auto [u, t] : (phase == 0? ::T[p]: ::A[p])) {
						if (t.first <= W[Q[l]] && W[Q[r-1]] < t.second) {
							dsu::unite(p, u);
							continue;
						}
						if (W[Q[r-1]] < t.first || t.second <= W[Q[l]])
							continue;
						E.push_back({{p,u},t});
					}
					p += phase == 0? 1: -1;
				}
				dsu::rec = 1;
				for (auto [e, t] : E) {
					if (t.first <= W[q] && W[q] <= t.second)
						dsu::unite(e.first, e.second);
				}
				ans[q] += dsu::cnt;
				dsu::rollback();
			}
			reverse(Q2.begin(), Q2.end());
		}
	}
	Loop (i,0,Q.size())
		ans[i] = n - ans[i];
	return vector<int>(ans, ans+Q.size());
}

Compilation message

collapse.cpp: In function 'void make_graph(std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:4:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
collapse.cpp:59:2: note: in expansion of macro 'Loop'
   59 |  Loop (i,0,t.size()) {
      |  ^~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int l = 0, r = 0; l < W.size(); l = r) {
      |                         ~~^~~~~~~~~~
collapse.cpp:97:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   while (r < W.size() && W[Q[r]] - W[Q[l]] <= S)
      |          ~~^~~~~~~~~~
collapse.cpp:4:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
      |                                          ^
collapse.cpp:131:2: note: in expansion of macro 'Loop'
  131 |  Loop (i,0,Q.size())
      |  ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6228 KB Output is correct
2 Incorrect 4 ms 5972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8980 KB Output is correct
2 Incorrect 26 ms 9024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9012 KB Output is correct
2 Correct 29 ms 8976 KB Output is correct
3 Correct 34 ms 9100 KB Output is correct
4 Correct 39 ms 9104 KB Output is correct
5 Correct 174 ms 9292 KB Output is correct
6 Correct 270 ms 9972 KB Output is correct
7 Correct 405 ms 18680 KB Output is correct
8 Correct 650 ms 22348 KB Output is correct
9 Correct 33 ms 9412 KB Output is correct
10 Correct 358 ms 9620 KB Output is correct
11 Correct 885 ms 22728 KB Output is correct
12 Correct 1202 ms 23200 KB Output is correct
13 Correct 902 ms 22908 KB Output is correct
14 Correct 1195 ms 23188 KB Output is correct
15 Correct 870 ms 22780 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6228 KB Output is correct
2 Incorrect 4 ms 5972 KB Output isn't correct
3 Halted 0 ms 0 KB -