oj.uz

답안 #129276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129276 2019-07-12T01:13:17 Z qkxwsm Collapse (JOI18_collapse) C++14
30 / 100
 11358 ms 29460 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;
unordered_set<int> edges[MAXN];
unordered_set<int> ins[MAXN];
vector<array<int, 4> > events;
vector<array<int, 4> > block;
vi ord;

bool cmp(int a, int b)
{
	return block[a][2] < block[b][2];
}
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];

void proc()
{
	D[0].init(); D[1].init();
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 1)
		{
			int u = block[i][2], v = block[i][3];
			if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
		}
	}
	int cp = -1, cc = 0;
	ord.clear();
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) ord.PB(i);
	}
	sort(ALL(ord), cmp);
	for (int idx : ord)
	{
		int t = block[idx][0], x = block[idx][2], qid = block[idx][3];
		while(cp < x)
		{
			cp++; cc++;
			for (int w : edges[cp]) if (D[0].merge(cp, w)) cc--;
		}
		// cerr << "cc = " << cc << endl;
		int res = cc;
		FOR(j, 0, SZ(block))
		{
			if (block[j][0] > t) break;
			if (block[j][1] == 2) continue;
			int u = block[j][2], v = block[j][3];
			if (v > x) continue;
			if (block[j][1] == 1)
			{
				if (ins[v].find(u) != ins[v].end()) ins[v].erase(u);
			}
			else
			{
				ins[v].insert(u);
			}
		}
		FOR(j, 0, SZ(block))
		{
			if (block[j][0] > t) break;
			if (block[j][1] == 2) continue;
			int u = block[j][2], v = block[j][3];
			if (v > x) continue;
			for (int w : ins[v])
			{
				// cerr << "merge " << v << ' ' << w << endl;
				if (D[1].merge(D[0].get(v), D[0].get(w))) res--;
			}
			ins[v].clear();
		}
		FOR(j, 0, SZ(block))
		{
			int u = block[j][2], v = block[j][3];
			u = D[0].get(u);
			D[1].dsu[u] = u; D[1].siz[u] = 1;
			v = D[0].get(v);
			D[1].dsu[v] = v; D[1].siz[v] = 1;
		}
		// cerr << res << endl;
		ans[qid] += res;
	}
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) continue;
		int u = block[i][2], v = block[i][3];
		if (block[i][1] == 1)
		{
			if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
		}
		else
		{
			edges[v].insert(u);
		}
	}
	//build the set of edges now!
}
void solve()
{
	//find # of cc's with value LESS THAN whatever
	//sort all the queries in the block.
	//after processing the block, the sets should store all active edges.
	// FOR(i, 0, SZ(events))
	// {
	// 	assert(events[i][1] == 2 || events[i][2] < events[i][3]);
	// }
	for (int i = 0; i < SZ(events); i += MAGIC)
	{
		for (int j = i; j < SZ(events) && j < i + MAGIC; j++)
		{
			block.PB(events[j]);
		}
		proc();
		block.clear();
	}
}
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;
	}
	// cerr << "SOLVE\n";
	solve();
	FOR(i, 0, N)
	{
		edges[i].clear();
		ins[i].clear();
	}
	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]);
		}
	}
	// cerr << "SOLVE\n";
	solve();
	return ans;
	//event: disconnect u -> v, connect u -> v, ask qid x pos y: so you store time, typ, who it happens to
	return ans;
}

Compilation message

collapse.cpp: In function 'void proc()':
collapse.cpp:129:8: warning: unused variable 'u' [-Wunused-variable]
    int u = block[j][2], v = block[j][3];
        ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 11900 KB Output is correct
2 Incorrect 92 ms 11768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1601 ms 15648 KB Output is correct
2 Incorrect 1667 ms 15692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1576 ms 15760 KB Output is correct
2 Correct 1740 ms 15636 KB Output is correct
3 Correct 1840 ms 15692 KB Output is correct
4 Correct 1914 ms 15692 KB Output is correct
5 Correct 1919 ms 15680 KB Output is correct
6 Correct 2003 ms 16092 KB Output is correct
7 Correct 3560 ms 22072 KB Output is correct
8 Correct 5150 ms 24792 KB Output is correct
9 Correct 1966 ms 16876 KB Output is correct
10 Correct 3162 ms 17244 KB Output is correct
11 Correct 8901 ms 28960 KB Output is correct
12 Correct 11358 ms 29460 KB Output is correct
13 Correct 8836 ms 28960 KB Output is correct
14 Correct 11194 ms 29304 KB Output is correct
15 Correct 8759 ms 29084 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 11900 KB Output is correct
2 Incorrect 92 ms 11768 KB Output isn't correct
3 Halted 0 ms 0 KB -