oj.uz

Submission #99578

# Submission time Handle Problem Language Result Execution time Memory
99578 2019-03-05T11:39:41 Z youngyojun Collapse (JOI18_collapse) C++11
0 / 100
 6809 ms 22128 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 = M, 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8320 KB Output is correct
2 Correct 12 ms 8064 KB Output is correct
3 Correct 12 ms 8064 KB Output is correct
4 Correct 13 ms 8064 KB Output is correct
5 Correct 30 ms 8260 KB Output is correct
6 Correct 34 ms 8440 KB Output is correct
7 Incorrect 13 ms 8064 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10800 KB Output is correct
2 Correct 74 ms 10800 KB Output is correct
3 Correct 464 ms 16748 KB Output is correct
4 Correct 114 ms 10996 KB Output is correct
5 Correct 698 ms 17184 KB Output is correct
6 Correct 142 ms 11640 KB Output is correct
7 Correct 1526 ms 21656 KB Output is correct
8 Correct 644 ms 19308 KB Output is correct
9 Incorrect 148 ms 11252 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 10868 KB Output is correct
2 Correct 77 ms 10868 KB Output is correct
3 Correct 77 ms 10912 KB Output is correct
4 Correct 94 ms 10868 KB Output is correct
5 Correct 92 ms 11220 KB Output is correct
6 Correct 148 ms 11668 KB Output is correct
7 Correct 1735 ms 19060 KB Output is correct
8 Correct 6809 ms 22128 KB Output is correct
9 Incorrect 165 ms 11252 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8320 KB Output is correct
2 Correct 12 ms 8064 KB Output is correct
3 Correct 12 ms 8064 KB Output is correct
4 Correct 13 ms 8064 KB Output is correct
5 Correct 30 ms 8260 KB Output is correct
6 Correct 34 ms 8440 KB Output is correct
7 Incorrect 13 ms 8064 KB Output isn't correct
8 Halted 0 ms 0 KB -