oj.uz

Submission #126685

# Submission time Handle Problem Language Result Execution time Memory
126685 2019-07-08T09:13:24 Z E869120 Collapse (JOI18_collapse) C++14
0 / 100
 2358 ms 29304 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 = 1009;

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[u] = v;
		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 8440 KB Output is correct
2 Incorrect 8 ms 5880 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 10076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9964 KB Output is correct
2 Correct 42 ms 9844 KB Output is correct
3 Correct 54 ms 10104 KB Output is correct
4 Correct 67 ms 10228 KB Output is correct
5 Correct 1411 ms 10108 KB Output is correct
6 Correct 2358 ms 29304 KB Output is correct
7 Runtime error 68 ms 17144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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