oj.uz

Submission #99579

# Submission time Handle Problem Language Result Execution time Memory
99579 2019-03-05T11:41:55 Z youngyojun Collapse (JOI18_collapse) C++11
35 / 100
 15000 ms 24512 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 100055;
const int MAXM = 100055;
const int MAXT = 100055;
const int MAXQ = 200055;
const int SQRQ = 450;

struct DJF {
	int ud[MAXN], h[MAXN], cnt;
	int rp[SQRQ*2], rv[SQRQ*2], n;

	void init() {
		iota(ud, ud+MAXN, 0);
		cnt = 0;
	}

	int _uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
	void _uf(int a, int b) {
		a = _uf(a); b = _uf(b);
		if(a == b) return;
		cnt++;
		ud[b] = a;
	}

	int uf(int i) {
		for(; i != ud[i]; i = ud[i]);
		return i;
	}
	void uf(int a, int b) {
		a = uf(a); b = uf(b);
		if(a == b) return;
		cnt++;
		if(h[a] < h[b]) swap(a, b);
		rp[n] = a; rv[n] = b; n++;
		ud[b] = a;
		if(h[a] == h[b]) h[a]++;
	}
	void roll() {
		for(int a, b; n--;) {
			cnt--;
			a = rp[n]; b = rv[n];
			h[a] = 0;
			ud[b] = b;
		}
		n = 0;
	}
} djf;

struct QUR {
	QUR(int day = 0, int t = 0, int dt = 0)
		: day(day), t(t), dt(dt) {}
	int day, t, dt;

	bool operator < (const QUR &q) const {
		if(day != q.day) return day < q.day;
		return t < q.t;
	}
} qur[MAXQ];

bitset<MAXM> ison, chk;

vector<int> TE[MAXM], G[MAXN];
int A[MAXM], B[MAXM];

int Ans[MAXT];
int N, M, T, Q;

int f(int e, int d) {
	return int(upper_bound(allv(TE[e]), d) - TE[e].begin());
}

void solve() {
	for(int s = 0, e = SQRQ; s < Q; s += SQRQ, e += SQRQ) {
		if(Q < e) e = Q;
		ison.reset(); chk.reset();
		for(int i = 0, t; i < s; i++) if(qur[i].t < 0) {
			t = qur[i].dt;
			ison[t] = !ison[t];
		}
		vector<int> EV, QV;
		for(int i = s, t; i < e; i++) {
			if(qur[i].t < 0) {
				t = qur[i].dt;
				if(chk[t]) continue;
				ison[t] = false;
				chk[t] = true;
				EV.eb(t);
			} else QV.eb(i);
		}
		sort(allv(QV), [&](int a, int b) {
			return qur[a].dt < qur[b].dt;
		});

		for(int i = 0; i < N; i++) G[i].clear();
		djf.init();

		for(int i = 0; i < M; i++) if(ison[i]) G[B[i]].eb(i);
		for(int oi = 0, i, px = 0, x, qvn = sz(QV); oi < qvn; oi++) {
			i = QV[oi]; x = qur[i].dt;
			for(; px < x;) {
				px++;
				for(int ed : G[px])
					djf._uf(A[ed], B[ed]);
			}
			for(int ed : EV) if((f(ed, qur[i].day)&1) && B[ed] <= x)
				djf.uf(A[ed], B[ed]);
			Ans[qur[i].t] += djf.cnt;
			djf.roll();
		}

		for(int i = 0; i < N; i++) G[i].clear();
		djf.init();
		revv(QV);

		for(int i = 0; i < M; i++) if(ison[i]) G[A[i]].eb(i);
		for(int oi = 0, i, px = N, x, qvn = sz(QV); oi < qvn; oi++) {
			i = QV[oi]; x = qur[i].dt;
			for(; x < px; px--) for(int ed : G[px])
				djf._uf(A[ed], B[ed]);
			for(int ed : EV) if((f(ed, qur[i].day)&1) && x < A[ed])
				djf.uf(A[ed], B[ed]);
			Ans[qur[i].t] += djf.cnt;
			djf.roll();
		}
	}
}

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
) {
	vector<pii> EV, TV;

	N = _N; M = sz(_T); T = sz(_W);
	for(int i = 0, a, b, c; i < M; i++) {
		a = _T[i]; b = _X[i]; c = _Y[i];
		if(b > c) swap(b, c);
		TV.eb(b, c);
	}
	EV = TV; sorv(EV); univ(EV);
	for(int i = 0, a, b, c; i < M; i++) {
		tie(a, b) = TV[i];
		c = int(lower_bound(allv(EV), pii(a, b)) - EV.begin());
		qur[i] = QUR(i, -1, c);
		TE[c].eb(i);
	}

	for(int i = 0, a, b; i < T; i++) {
		a = _W[i]; b = _P[i];
		qur[M+i] = QUR(a, i, b);
	}

	Q = M+T;
	M = sz(EV);
	for(int i = 0; i < M; i++)
		tie(A[i], B[i]) = EV[i];

	sort(qur, qur+Q);

	solve();

	vector<int> ret;
	for(int i = 0; i < T; i++) ret.eb(N - Ans[i]);
	return ret;
}

Compilation message

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:149:17: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  for(int i = 0, a, b, c; i < M; i++) {
                 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 12 ms 7936 KB Output is correct
3 Correct 13 ms 7936 KB Output is correct
4 Correct 16 ms 7936 KB Output is correct
5 Correct 26 ms 8192 KB Output is correct
6 Correct 42 ms 8396 KB Output is correct
7 Correct 12 ms 8092 KB Output is correct
8 Correct 13 ms 8064 KB Output is correct
9 Correct 27 ms 8440 KB Output is correct
10 Correct 52 ms 8568 KB Output is correct
11 Correct 48 ms 8668 KB Output is correct
12 Correct 53 ms 8696 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10408 KB Output is correct
2 Correct 84 ms 10456 KB Output is correct
3 Correct 475 ms 15216 KB Output is correct
4 Correct 86 ms 10484 KB Output is correct
5 Correct 780 ms 15468 KB Output is correct
6 Correct 133 ms 10872 KB Output is correct
7 Correct 1315 ms 19712 KB Output is correct
8 Correct 618 ms 16876 KB Output is correct
9 Correct 154 ms 10456 KB Output is correct
10 Correct 183 ms 11316 KB Output is correct
11 Correct 185 ms 12020 KB Output is correct
12 Correct 895 ms 20372 KB Output is correct
13 Correct 2682 ms 22388 KB Output is correct
14 Correct 4590 ms 24224 KB Output is correct
15 Correct 4866 ms 24408 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10540 KB Output is correct
2 Correct 91 ms 10456 KB Output is correct
3 Correct 78 ms 10488 KB Output is correct
4 Correct 90 ms 10468 KB Output is correct
5 Correct 92 ms 10484 KB Output is correct
6 Correct 187 ms 10976 KB Output is correct
7 Correct 1669 ms 17384 KB Output is correct
8 Correct 6781 ms 19880 KB Output is correct
9 Correct 176 ms 10360 KB Output is correct
10 Correct 227 ms 11892 KB Output is correct
11 Correct 14381 ms 24216 KB Output is correct
12 Correct 13222 ms 24512 KB Output is correct
13 Execution timed out 15047 ms 23168 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8192 KB Output is correct
2 Correct 12 ms 7936 KB Output is correct
3 Correct 13 ms 7936 KB Output is correct
4 Correct 16 ms 7936 KB Output is correct
5 Correct 26 ms 8192 KB Output is correct
6 Correct 42 ms 8396 KB Output is correct
7 Correct 12 ms 8092 KB Output is correct
8 Correct 13 ms 8064 KB Output is correct
9 Correct 27 ms 8440 KB Output is correct
10 Correct 52 ms 8568 KB Output is correct
11 Correct 48 ms 8668 KB Output is correct
12 Correct 53 ms 8696 KB Output is correct
13 Correct 78 ms 10408 KB Output is correct
14 Correct 84 ms 10456 KB Output is correct
15 Correct 475 ms 15216 KB Output is correct
16 Correct 86 ms 10484 KB Output is correct
17 Correct 780 ms 15468 KB Output is correct
18 Correct 133 ms 10872 KB Output is correct
19 Correct 1315 ms 19712 KB Output is correct
20 Correct 618 ms 16876 KB Output is correct
21 Correct 154 ms 10456 KB Output is correct
22 Correct 183 ms 11316 KB Output is correct
23 Correct 185 ms 12020 KB Output is correct
24 Correct 895 ms 20372 KB Output is correct
25 Correct 2682 ms 22388 KB Output is correct
26 Correct 4590 ms 24224 KB Output is correct
27 Correct 4866 ms 24408 KB Output is correct
28 Correct 84 ms 10540 KB Output is correct
29 Correct 91 ms 10456 KB Output is correct
30 Correct 78 ms 10488 KB Output is correct
31 Correct 90 ms 10468 KB Output is correct
32 Correct 92 ms 10484 KB Output is correct
33 Correct 187 ms 10976 KB Output is correct
34 Correct 1669 ms 17384 KB Output is correct
35 Correct 6781 ms 19880 KB Output is correct
36 Correct 176 ms 10360 KB Output is correct
37 Correct 227 ms 11892 KB Output is correct
38 Correct 14381 ms 24216 KB Output is correct
39 Correct 13222 ms 24512 KB Output is correct
40 Execution timed out 15047 ms 23168 KB Time limit exceeded
41 Halted 0 ms 0 KB -