oj.uz

Submission #129657

# Submission time Handle Problem Language Result Execution time Memory
129657 2019-07-12T22:31:00 Z qkxwsm Collapse (JOI18_collapse) C++14
35 / 100
 14821 ms 524292 KB 
#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969
#define MAXN 400013
#define MAGIC 521

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
vi ans;
vector<array<int, 4> > events;
int die[MAXN];
vi ord, cand;
vi ch[MAXN];
map<int, int> rec[MAXN];

struct dsu
{
	int dsu[MAXN], siz[MAXN];
	vi edits;
	void init()
	{
		FOR(i, 0, N)
		{
			dsu[i] = i;
			siz[i] = 1;
		}
	}
	void rollback()
	{
		for (int x : edits)
		{
			dsu[x] = x;
			siz[x] = 1;
		}
		edits.clear();
	}
	int get(int u)
	{
		if (u == dsu[u]) return u;
		int v = get(dsu[u]);
		edits.PB(u);
		dsu[u] = v;
		return v;
	}
	bool merge(int u, int v)
	{
		u = get(u); v = get(v);
		if (u == v) return false;
		if (siz[u] > siz[v]) swap(u, v);
		siz[v] += siz[u];
		dsu[u] = v;
		edits.PB(u);
		return true;
	}
};

dsu D[2];

bool cmp(int a, int b)
{
	return events[a][2] < events[b][2];
}

void proc(int l, int r)
{
	//build the set of edges now!
	D[0].init(); D[1].init();
	cand.clear(); ord.clear();
	FOR(i, 0, N)
	{
		ch[i].clear();
	}
	FOR(i, l, r + 1)
	{
		if (events[i][1] == 2)
		{
			ord.PB(i);
		}
	}
	sort(ALL(ord), cmp);
	FOR(i, 0, l)
	{
		if (events[i][1] != 0) continue;
		int u = events[i][2], v = events[i][3];
		if (die[i] <= r) cand.PB(i);
		else
		{
			ch[v].PB(u);
		}
	}
	int cc = 0, cp = 0;
	for (int p : ord)
	{
		int u = events[p][2], qid = events[p][3], t = events[p][0];
		while(cp <= u)
		{
			cc++;
			for (int v : ch[cp])
			{
				if (D[0].merge(cp, v)) cc--;
			}
			cp++;
		}
		int res = cc;
		for (int x : cand)
		{
			int v = events[x][2], w = events[x][3];
			if (die[x] > t && w <= u)
			{
				v = D[0].get(v); w = D[0].get(w);
				if (D[1].merge(v, w)) res--;
			}
		}
		FOR(j, l, p)
		{
			if (events[j][1] != 0) continue;
			int v = events[j][2], w = events[j][3];
			if (die[j] > t && w <= u)
			{
				v = D[0].get(v); w = D[0].get(w);
				if (D[1].merge(v, w)) res--;
			}
		}
		D[1].rollback();
		ans[qid] += res;
	}
	return;
}
void solve()
{
	FOR(i, 0, N) rec[i].clear();
	FOR(i, 0, SZ(events))
	{
		if (events[i][1] == 2) continue;
		if (events[i][1] == 0)
		{
			rec[events[i][2]][events[i][3]] = i;
			die[i] = SZ(events);
		}
		else
		{
			die[rec[events[i][2]][events[i][3]]] = i;
		}
	}
	for (int i = 0; i < SZ(events); i += MAGIC)
	{
		proc(i, min(i + MAGIC, SZ(events)) - 1);
	}
}
vi simulateCollapse(int n, vi t, vi x, vi y, vi w, vi p)
{
	N = n; Q = SZ(w);
	ans.resize(Q);
	FOR(i, 0, SZ(t))
	{
		if (x[i] > y[i]) swap(x[i], y[i]);
		events.PB({i, t[i], x[i], y[i]});
	}
	FOR(i, 0, Q)
	{
		events.PB({w[i], 2, p[i], i});
	}
	sort(ALL(events));
	FOR(i, 0, SZ(events))
	{
		events[i][0] = i;
	}
	//hm ok each edge has a birth and death time.
	solve();
	for (auto &e : events)
	{
		if (e[1] == 2)
		{
			e[2] = N - 2 - e[2];
		}
		else
		{
			e[2] = N - 1 - e[2];
			e[3] = N - 1 - e[3];
			swap(e[2], e[3]);
		}
	}
	solve();
	return ans;
	//event: disconnect u -> v, connect u -> v, ask qid x pos y: so you store time, typ, who it happens to
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 29176 KB Output is correct
2 Correct 33 ms 28792 KB Output is correct
3 Correct 34 ms 28920 KB Output is correct
4 Correct 34 ms 28920 KB Output is correct
5 Correct 64 ms 29176 KB Output is correct
6 Correct 57 ms 33508 KB Output is correct
7 Correct 35 ms 29048 KB Output is correct
8 Correct 35 ms 29048 KB Output is correct
9 Correct 67 ms 29432 KB Output is correct
10 Correct 81 ms 31484 KB Output is correct
11 Correct 64 ms 31596 KB Output is correct
12 Correct 64 ms 33640 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 32600 KB Output is correct
2 Correct 187 ms 32720 KB Output is correct
3 Correct 13911 ms 38708 KB Output is correct
4 Correct 206 ms 33256 KB Output is correct
5 Correct 14000 ms 59416 KB Output is correct
6 Correct 304 ms 42100 KB Output is correct
7 Correct 1544 ms 306908 KB Output is correct
8 Correct 14086 ms 42916 KB Output is correct
9 Correct 419 ms 34792 KB Output is correct
10 Correct 422 ms 34920 KB Output is correct
11 Correct 525 ms 36176 KB Output is correct
12 Correct 14821 ms 44656 KB Output is correct
13 Correct 11995 ms 113884 KB Output is correct
14 Correct 3148 ms 181212 KB Output is correct
15 Correct 2752 ms 181288 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 32624 KB Output is correct
2 Correct 191 ms 32752 KB Output is correct
3 Correct 191 ms 33072 KB Output is correct
4 Correct 191 ms 33308 KB Output is correct
5 Correct 215 ms 36492 KB Output is correct
6 Correct 337 ms 50236 KB Output is correct
7 Correct 2000 ms 303532 KB Output is correct
8 Runtime error 2842 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 29176 KB Output is correct
2 Correct 33 ms 28792 KB Output is correct
3 Correct 34 ms 28920 KB Output is correct
4 Correct 34 ms 28920 KB Output is correct
5 Correct 64 ms 29176 KB Output is correct
6 Correct 57 ms 33508 KB Output is correct
7 Correct 35 ms 29048 KB Output is correct
8 Correct 35 ms 29048 KB Output is correct
9 Correct 67 ms 29432 KB Output is correct
10 Correct 81 ms 31484 KB Output is correct
11 Correct 64 ms 31596 KB Output is correct
12 Correct 64 ms 33640 KB Output is correct
13 Correct 177 ms 32600 KB Output is correct
14 Correct 187 ms 32720 KB Output is correct
15 Correct 13911 ms 38708 KB Output is correct
16 Correct 206 ms 33256 KB Output is correct
17 Correct 14000 ms 59416 KB Output is correct
18 Correct 304 ms 42100 KB Output is correct
19 Correct 1544 ms 306908 KB Output is correct
20 Correct 14086 ms 42916 KB Output is correct
21 Correct 419 ms 34792 KB Output is correct
22 Correct 422 ms 34920 KB Output is correct
23 Correct 525 ms 36176 KB Output is correct
24 Correct 14821 ms 44656 KB Output is correct
25 Correct 11995 ms 113884 KB Output is correct
26 Correct 3148 ms 181212 KB Output is correct
27 Correct 2752 ms 181288 KB Output is correct
28 Correct 178 ms 32624 KB Output is correct
29 Correct 191 ms 32752 KB Output is correct
30 Correct 191 ms 33072 KB Output is correct
31 Correct 191 ms 33308 KB Output is correct
32 Correct 215 ms 36492 KB Output is correct
33 Correct 337 ms 50236 KB Output is correct
34 Correct 2000 ms 303532 KB Output is correct
35 Runtime error 2842 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Halted 0 ms 0 KB -