oj.uz

Submission #129648

# Submission time Handle Problem Language Result Execution time Memory
129648 2019-07-12T21:47:28 Z qkxwsm Collapse (JOI18_collapse) C++14
5 / 100
 1783 ms 32228 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 100013
#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 95 ms 8056 KB Output is correct
2 Correct 70 ms 7672 KB Output is correct
3 Correct 72 ms 7800 KB Output is correct
4 Correct 72 ms 7800 KB Output is correct
5 Correct 104 ms 8184 KB Output is correct
6 Correct 90 ms 8252 KB Output is correct
7 Correct 68 ms 7800 KB Output is correct
8 Correct 73 ms 7800 KB Output is correct
9 Correct 109 ms 8188 KB Output is correct
10 Correct 120 ms 8288 KB Output is correct
11 Correct 109 ms 8440 KB Output is correct
12 Correct 102 ms 8440 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1470 ms 12172 KB Output is correct
2 Correct 1351 ms 12220 KB Output is correct
3 Runtime error 110 ms 32228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1296 ms 12224 KB Output is correct
2 Correct 1500 ms 12208 KB Output is correct
3 Correct 1665 ms 12272 KB Output is correct
4 Correct 1712 ms 12388 KB Output is correct
5 Correct 1783 ms 12824 KB Output is correct
6 Runtime error 69 ms 24320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 8056 KB Output is correct
2 Correct 70 ms 7672 KB Output is correct
3 Correct 72 ms 7800 KB Output is correct
4 Correct 72 ms 7800 KB Output is correct
5 Correct 104 ms 8184 KB Output is correct
6 Correct 90 ms 8252 KB Output is correct
7 Correct 68 ms 7800 KB Output is correct
8 Correct 73 ms 7800 KB Output is correct
9 Correct 109 ms 8188 KB Output is correct
10 Correct 120 ms 8288 KB Output is correct
11 Correct 109 ms 8440 KB Output is correct
12 Correct 102 ms 8440 KB Output is correct
13 Correct 1470 ms 12172 KB Output is correct
14 Correct 1351 ms 12220 KB Output is correct
15 Runtime error 110 ms 32228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -