oj.uz

Submission #129660

# Submission time Handle Problem Language Result Execution time Memory
129660 2019-07-12T22:46:40 Z qkxwsm Collapse (JOI18_collapse) C++14
35 / 100
 15000 ms 307744 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 u : edits)
		{
			dsu[u] = u;
			siz[u] = 1;
		}
		edits.clear();
	}
	int get(int u)
	{
		return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
	}
	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();
	vector<array<int, 4> > ihateconstantoptimize;
	FOR(j, l, r + 1)
	{
		if (events[j][1] != 0) continue;
		ihateconstantoptimize.PB(events[j]);
	}
	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 (auto e : ihateconstantoptimize)
		{
			if (e[0] > t) break;
			int v = e[2], w = e[3];
			if (die[e[0]] > 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, 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(i, 0, N) rec[i].clear();
	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 57 ms 29176 KB Output is correct
2 Correct 30 ms 28792 KB Output is correct
3 Correct 30 ms 28920 KB Output is correct
4 Correct 36 ms 28792 KB Output is correct
5 Correct 63 ms 29176 KB Output is correct
6 Correct 43 ms 29196 KB Output is correct
7 Correct 31 ms 29048 KB Output is correct
8 Correct 31 ms 28920 KB Output is correct
9 Correct 63 ms 29248 KB Output is correct
10 Correct 71 ms 29296 KB Output is correct
11 Correct 54 ms 29764 KB Output is correct
12 Correct 52 ms 29788 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 32620 KB Output is correct
2 Correct 136 ms 32748 KB Output is correct
3 Correct 13864 ms 37684 KB Output is correct
4 Correct 137 ms 32748 KB Output is correct
5 Correct 13989 ms 37556 KB Output is correct
6 Correct 175 ms 33388 KB Output is correct
7 Correct 951 ms 43016 KB Output is correct
8 Correct 14300 ms 39824 KB Output is correct
9 Correct 362 ms 34024 KB Output is correct
10 Correct 374 ms 34088 KB Output is correct
11 Correct 492 ms 34896 KB Output is correct
12 Execution timed out 15018 ms 41388 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 32620 KB Output is correct
2 Correct 137 ms 32732 KB Output is correct
3 Correct 140 ms 32748 KB Output is correct
4 Correct 140 ms 32748 KB Output is correct
5 Correct 154 ms 33256 KB Output is correct
6 Correct 198 ms 33612 KB Output is correct
7 Correct 1070 ms 44000 KB Output is correct
8 Correct 2275 ms 75272 KB Output is correct
9 Correct 380 ms 34152 KB Output is correct
10 Correct 443 ms 35944 KB Output is correct
11 Correct 4501 ms 176220 KB Output is correct
12 Correct 5529 ms 307744 KB Output is correct
13 Correct 4038 ms 176128 KB Output is correct
14 Correct 5650 ms 307724 KB Output is correct
15 Correct 4101 ms 176160 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 29176 KB Output is correct
2 Correct 30 ms 28792 KB Output is correct
3 Correct 30 ms 28920 KB Output is correct
4 Correct 36 ms 28792 KB Output is correct
5 Correct 63 ms 29176 KB Output is correct
6 Correct 43 ms 29196 KB Output is correct
7 Correct 31 ms 29048 KB Output is correct
8 Correct 31 ms 28920 KB Output is correct
9 Correct 63 ms 29248 KB Output is correct
10 Correct 71 ms 29296 KB Output is correct
11 Correct 54 ms 29764 KB Output is correct
12 Correct 52 ms 29788 KB Output is correct
13 Correct 127 ms 32620 KB Output is correct
14 Correct 136 ms 32748 KB Output is correct
15 Correct 13864 ms 37684 KB Output is correct
16 Correct 137 ms 32748 KB Output is correct
17 Correct 13989 ms 37556 KB Output is correct
18 Correct 175 ms 33388 KB Output is correct
19 Correct 951 ms 43016 KB Output is correct
20 Correct 14300 ms 39824 KB Output is correct
21 Correct 362 ms 34024 KB Output is correct
22 Correct 374 ms 34088 KB Output is correct
23 Correct 492 ms 34896 KB Output is correct
24 Execution timed out 15018 ms 41388 KB Time limit exceeded
25 Halted 0 ms 0 KB -