oj.uz

Submission #129649

# Submission time Handle Problem Language Result Execution time Memory
129649 2019-07-12T21:47:59 Z qkxwsm Collapse (JOI18_collapse) C++14
35 / 100
 15000 ms 48628 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(j, l, r + 1)
		{
			int v = events[j][2], w = events[j][3];
			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 120 ms 29048 KB Output is correct
2 Correct 92 ms 28904 KB Output is correct
3 Correct 91 ms 28920 KB Output is correct
4 Correct 91 ms 28892 KB Output is correct
5 Correct 119 ms 29176 KB Output is correct
6 Correct 115 ms 29320 KB Output is correct
7 Correct 94 ms 28920 KB Output is correct
8 Correct 93 ms 28924 KB Output is correct
9 Correct 133 ms 29304 KB Output is correct
10 Correct 146 ms 29312 KB Output is correct
11 Correct 130 ms 29452 KB Output is correct
12 Correct 128 ms 29452 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1522 ms 32920 KB Output is correct
2 Correct 1353 ms 32872 KB Output is correct
3 Execution timed out 15047 ms 37888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 32892 KB Output is correct
2 Correct 1516 ms 32924 KB Output is correct
3 Correct 1686 ms 32972 KB Output is correct
4 Correct 1748 ms 33068 KB Output is correct
5 Correct 1822 ms 33256 KB Output is correct
6 Correct 1847 ms 33880 KB Output is correct
7 Correct 2629 ms 42268 KB Output is correct
8 Correct 4045 ms 45852 KB Output is correct
9 Correct 2159 ms 34860 KB Output is correct
10 Correct 2863 ms 35532 KB Output is correct
11 Correct 6761 ms 48536 KB Output is correct
12 Correct 8696 ms 48440 KB Output is correct
13 Correct 6801 ms 48376 KB Output is correct
14 Correct 9584 ms 48628 KB Output is correct
15 Correct 6157 ms 48560 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 29048 KB Output is correct
2 Correct 92 ms 28904 KB Output is correct
3 Correct 91 ms 28920 KB Output is correct
4 Correct 91 ms 28892 KB Output is correct
5 Correct 119 ms 29176 KB Output is correct
6 Correct 115 ms 29320 KB Output is correct
7 Correct 94 ms 28920 KB Output is correct
8 Correct 93 ms 28924 KB Output is correct
9 Correct 133 ms 29304 KB Output is correct
10 Correct 146 ms 29312 KB Output is correct
11 Correct 130 ms 29452 KB Output is correct
12 Correct 128 ms 29452 KB Output is correct
13 Correct 1522 ms 32920 KB Output is correct
14 Correct 1353 ms 32872 KB Output is correct
15 Execution timed out 15047 ms 37888 KB Time limit exceeded
16 Halted 0 ms 0 KB -