oj.uz

Submission #126725

# Submission time Handle Problem Language Result Execution time Memory
126725 2019-07-08T09:56:14 Z E869120 Collapse (JOI18_collapse) C++14
0 / 100
 15000 ms 8700 KB 
#include "collapse.h"
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class UnionFind {
public:
	vector<int> par;

	void init(int sz) {
		par.clear();
		par.resize(sz, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

const int Backet = 1;

int N, C, Q;
int T[100009], X[100009], Y[100009], W[100009], P[100009], num[100009], ans[100009];
vector<pair<int, int>> Edge;
UnionFind UF;

bool useda[100009], used[100009], usedb[100009];

void precise(int cl, int cr) {
	int connectivity = N;

	for (int i = 0; i <= 100000; i++) { used[i] = false; useda[i] = false; usedb[i] = false; }
	for (int i = 1; i < cl; i++) {
		if (T[i] == 0) used[num[i]] = true;
		if (T[i] == 1) used[num[i]] = false;
	}
	vector<int>vec;
	for (int i = cl; i <= cr; i++) { useda[num[i]] = true; vec.push_back(num[i]); }
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());

	UF.init(N + 2);
	for (int i = 0; i < Edge.size(); i++) {
		if (used[i] == true && useda[i] == false) {
			if (Edge[i].second <= P[1] || P[1] < Edge[i].first) {
				if (UF.same(Edge[i].first, Edge[i].second) == false) connectivity--;
				UF.unite(Edge[i].first, Edge[i].second);
			}
		}
	}

	for (int i = 0; i < vec.size(); i++) usedb[i] = used[vec[i]];

	for (int i = cl; i <= cr; i++) {
		int pos1 = lower_bound(vec.begin(), vec.end(), num[i]) - vec.begin();
		usedb[pos1] ^= true;

		vector<int>E; vector<pair<int, int>>F;
		for (int j = 0; j < vec.size(); j++) {
			if (usedb[j] == false) continue;
			int V = vec[j];
			int u1 = Edge[V].first, u2 = Edge[V].second;
			if (u2 <= P[1] || P[1] < u1) { E.push_back(u1); E.push_back(u2); F.push_back(make_pair(u1, u2)); }
		}
		sort(E.begin(), E.end());
		E.erase(unique(E.begin(), E.end()), E.end());

		UnionFind UF2; UF2.init(E.size()); int ret = connectivity;
		for (int j = 0; j < F.size(); j++) {
			int pos2 = lower_bound(E.begin(), E.end(), F[j].first) - E.begin();
			int pos3 = lower_bound(E.begin(), E.end(), F[j].second) - E.begin();
			if (UF2.same(pos2, pos3) == false) ret--;
			UF2.unite(pos2, pos3);
		}
		ans[i] = ret;
	}
}

vector<int> solve() {
	for (int i = 1; i <= C; i++) Edge.push_back(make_pair(X[i], Y[i]));
	sort(Edge.begin(), Edge.end());
	Edge.erase(unique(Edge.begin(), Edge.end()), Edge.end());
	for (int i = 1; i <= C; i++) num[i] = lower_bound(Edge.begin(), Edge.end(), make_pair(X[i], Y[i])) - Edge.begin();

	for (int i = 1; i <= C; i += Backet) {
		int el = i, er = i + Backet - 1; if (er > C) er = C;
		precise(el, er);
	}

	vector<int> J;
	for (int i = 1; i <= Q; i++) J.push_back(ans[W[i]]);
	return J;
}

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]); }

	return solve();
}

Compilation message

collapse.cpp: In function 'void precise(int, int)':
collapse.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Edge.size(); i++) {
                  ~~^~~~~~~~~~~~~
collapse.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) usedb[i] = used[vec[i]];
                  ~~^~~~~~~~~~~~
collapse.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); j++) {
                   ~~^~~~~~~~~~~~
collapse.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < F.size(); j++) {
                   ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3700 KB Output is correct
2 Correct 30 ms 3700 KB Output is correct
3 Execution timed out 15066 ms 8700 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3700 KB Output is correct
2 Incorrect 29 ms 3572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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