oj.uz

Submission #126689

# Submission time Handle Problem Language Result Execution time Memory
126689 2019-07-08T09:19:58 Z E869120 Collapse (JOI18_collapse) C++14
30 / 100
 7077 ms 492352 KB 
#include "collapse.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;

const int MAX_N = (1 << 17);
const int MAX_UF = 301;
const int BACKET = 1209;

class SuperiorRankUnionFind {
public:
	int query = 0, numedge = 0;
	vector<int> par, ranks;
	vector<pair<int, int>> G_par, G_ranks;

	void init(int sz) {
		query = 0; numedge = 0;
		par.resize(sz, -1);
		ranks.resize(sz, -1);
		G_par.resize(MAX_N, make_pair(-1, -1));
		G_ranks.resize(MAX_N, make_pair(-1, -1));
	}
	int root(int pos) {
		while (par[pos] != -1) {
			pos = par[pos];
		}
		return pos;
	}
	void unite(int u, int v) {
		query++;
		u = root(u); v = root(v);
		if (u == v) return;

		if (ranks[u] > ranks[v]) swap(u, v);

		G_par[query] = make_pair(u, par[u]);
		par[u] = v;
		G_ranks[query] = make_pair(u, ranks[u]);
		ranks[v] = max(ranks[v], ranks[u] + 1);
		numedge++;
	}
	void reversi() {
		if (G_par[query] != make_pair(-1, -1)) {
			pair<int, int> E = G_par[query];
			par[E.first] = E.second;
		}
		if (G_ranks[query] != make_pair(-1, -1)) {
			pair<int, int> E = G_ranks[query];
			ranks[E.first] = E.second;
		}
		if (G_par[query] != make_pair(-1, -1)) numedge--;
		G_par[query] = make_pair(-1, -1);
		G_ranks[query] = make_pair(-1, -1);
		query--;
	}
};

int SIZE_ = 1;
int N, C, Q, T[MAX_N], X[MAX_N], Y[MAX_N], W[MAX_N], P[MAX_N], ans[MAX_N];
vector<pair<int, int>> Question[MAX_N];
map<pair<int, int>, int> Map;

SuperiorRankUnionFind UF[MAX_UF]; int cnts, el[MAX_UF], er[MAX_UF], deg[MAX_N];
vector<tuple<int, int, int, int>> PossibleEdge[MAX_UF];

vector<int> solve() {
	// Step 1 : 幅を決める
	for (int i = 1; i <= C; i++) { deg[X[i]]++; deg[Y[i]]++; }

	int sum1 = 0, id = 1;
	for (int i = 1; i <= N; i++) {
		sum1 += deg[i];
		if (sum1 + deg[i + 1] > BACKET || i == N) {
			cnts++;
			el[cnts] = id;
			er[cnts] = i;
			sum1 = 0; id = i + 1;
		}
	}

	for (int i = 1; i <= C; i++) {
		for (int j = 1; j <= cnts; j++) {
			if ((el[j] <= X[i] && X[i] <= er[j]) || (el[j] <= Y[i] && Y[i] <= er[j])) {
				PossibleEdge[j].push_back(make_tuple(X[i], Y[i], i, C));
			}
		}
	}

	// Step 2 : 質問の設定
	for (int i = 1; i <= Q; i++) {
		Question[W[i]].push_back(make_pair(P[i], i));
	}
	for (int i = 1; i <= cnts; i++) UF[i].init(N + 2);

	// Step 3 : 探索
	for (int t = 1; t <= C; t++) {
		for (int i = 1; i <= cnts; i++) {
			if (Y[t] <= el[i] || er[i] < X[t]) UF[i].unite(X[t], Y[t]);
		}
		for (pair<int, int> que : Question[t]) {
			int p = que.first, id = -1;
			for (int i = 1; i <= cnts; i++) {
				if (el[i] <= p && p <= er[i]) id = i;
			}
			int cntv = 0;
			for (int i = 0; i < PossibleEdge[id].size(); i++) {
				tuple<int, int, int, int> H = PossibleEdge[id][i];
				if ((get<1>(H) <= p || p < get<0>(H)) && get<2>(H) <= t) {
					UF[id].unite(get<0>(H), get<1>(H)); cntv++;
				}
			}
			ans[que.second] = N - UF[id].numedge;
			for (int i = 1; i <= cntv; i++) UF[id].reversi();
		}
	}

	// Step 5 : 最終決定
	vector<int>FinalAns;
	for (int i = 1; i <= Q; i++) FinalAns.push_back(ans[i]);
	return FinalAns;
}

vector<int> simulateCollapse(int N1, vector<int>T1, vector<int>X1, vector<int>Y1, vector<int>W1, vector<int>P1) {
	N = N1; C = T1.size(); Q = W1.size();
	for (int i = 1; i <= C; i++) T[i] = T1[i - 1];
	for (int i = 1; i <= C; i++) { X[i] = X1[i - 1]; X[i]++; }
	for (int i = 1; i <= C; i++) { Y[i] = Y1[i - 1]; Y[i]++; }
	for (int i = 1; i <= Q; i++) { W[i] = W1[i - 1]; W[i]++; }
	for (int i = 1; i <= Q; i++) { P[i] = P1[i - 1]; P[i]++; }
	for (int i = 1; i <= C; i++) { if (X[i] > Y[i]) swap(X[i], Y[i]); }
	//assert(1LL * N * C * Q <= 10000LL * 10000LL * 10000LL);
	return solve();
}

Compilation message

collapse.cpp: In function 'std::vector<int> solve()':
collapse.cpp:109:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < PossibleEdge[id].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8312 KB Output is correct
2 Incorrect 8 ms 5756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9964 KB Output is correct
2 Incorrect 40 ms 10100 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 35 ms 9964 KB Output is correct
2 Correct 45 ms 9776 KB Output is correct
3 Correct 57 ms 10072 KB Output is correct
4 Correct 67 ms 10228 KB Output is correct
5 Correct 862 ms 10236 KB Output is correct
6 Correct 1429 ms 27124 KB Output is correct
7 Correct 2041 ms 288124 KB Output is correct
8 Correct 3579 ms 376396 KB Output is correct
9 Correct 47 ms 11500 KB Output is correct
10 Correct 940 ms 15076 KB Output is correct
11 Correct 3743 ms 321036 KB Output is correct
12 Correct 7077 ms 492352 KB Output is correct
13 Correct 4415 ms 386640 KB Output is correct
14 Correct 7010 ms 492232 KB Output is correct
15 Correct 3927 ms 338212 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8312 KB Output is correct
2 Incorrect 8 ms 5756 KB Output isn't correct
3 Halted 0 ms 0 KB -