oj.uz

Submission #129654

# Submission time Handle Problem Language Result Execution time Memory
129654 2019-07-12T22:11:31 Z qkxwsm Collapse (JOI18_collapse) C++14
35 / 100
 15000 ms 47884 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];
	void init()
	{
		FOR(i, 0, N)
		{
			dsu[i] = i;
			siz[i] = 1;
		}
	}
	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;
		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--;
			}
		}
		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);
				D[1].dsu[v] = v;
				D[1].siz[v] = 1;
				D[1].dsu[w] = w;
				D[1].siz[w] = 1;
			}
		}
		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);
				D[1].dsu[v] = v;
				D[1].siz[v] = 1;
				D[1].dsu[w] = w;
				D[1].siz[w] = 1;
			}
		}
		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 87 ms 29304 KB Output is correct
2 Correct 36 ms 28920 KB Output is correct
3 Correct 36 ms 28920 KB Output is correct
4 Correct 37 ms 28920 KB Output is correct
5 Correct 100 ms 29176 KB Output is correct
6 Correct 59 ms 29300 KB Output is correct
7 Correct 36 ms 29048 KB Output is correct
8 Correct 37 ms 29048 KB Output is correct
9 Correct 100 ms 29344 KB Output is correct
10 Correct 107 ms 29304 KB Output is correct
11 Correct 76 ms 29532 KB Output is correct
12 Correct 67 ms 29600 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 33032 KB Output is correct
2 Correct 239 ms 33132 KB Output is correct
3 Execution timed out 15077 ms 38852 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 33132 KB Output is correct
2 Correct 234 ms 33004 KB Output is correct
3 Correct 238 ms 33132 KB Output is correct
4 Correct 251 ms 33260 KB Output is correct
5 Correct 255 ms 33640 KB Output is correct
6 Correct 322 ms 34156 KB Output is correct
7 Correct 1353 ms 41952 KB Output is correct
8 Correct 2472 ms 44896 KB Output is correct
9 Correct 495 ms 34896 KB Output is correct
10 Correct 569 ms 35560 KB Output is correct
11 Correct 4417 ms 47884 KB Output is correct
12 Correct 5683 ms 47592 KB Output is correct
13 Correct 4713 ms 47820 KB Output is correct
14 Correct 5649 ms 47856 KB Output is correct
15 Correct 4077 ms 47764 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 29304 KB Output is correct
2 Correct 36 ms 28920 KB Output is correct
3 Correct 36 ms 28920 KB Output is correct
4 Correct 37 ms 28920 KB Output is correct
5 Correct 100 ms 29176 KB Output is correct
6 Correct 59 ms 29300 KB Output is correct
7 Correct 36 ms 29048 KB Output is correct
8 Correct 37 ms 29048 KB Output is correct
9 Correct 100 ms 29344 KB Output is correct
10 Correct 107 ms 29304 KB Output is correct
11 Correct 76 ms 29532 KB Output is correct
12 Correct 67 ms 29600 KB Output is correct
13 Correct 224 ms 33032 KB Output is correct
14 Correct 239 ms 33132 KB Output is correct
15 Execution timed out 15077 ms 38852 KB Time limit exceeded
16 Halted 0 ms 0 KB -