oj.uz

답안 #380870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380870 2021-03-23T12:15:58 Z qwerty234 Collapse (JOI18_collapse) C++14
5 / 100
 496 ms 1920 KB 
#include <bits/stdc++.h>
#include "collapse.h"
#define pb push_back
#define fi first
#define se second
using namespace std;

const int blocksz = 5010;

struct query {
	int plan_day, collapse_town, id;
	query(int x, int y, int z) {plan_day = x; collapse_town = y; id = z;}
};
bool cmpquery(query A, query B) {return A.plan_day < B.plan_day;}

struct operation {
	int u, v, sz_u, sz_v;
	operation(int x, int y, int z, int d) {u = x; v = y; sz_u = z; sz_v = d;}
};
vector <int> sz, p;
vector <operation> op;
int sz_comp;

void make_set(int n) {
	sz.assign(n, 1); p.assign(n, 0); op.clear();
	for (int i = 0; i < n; i++) p[i] = i;
	sz_comp = n;
}

int getp(int u) {
	if (p[u] == u) return u;
	return getp(p[u]);
}

int add(int u, int v) {
	u = getp(u); v = getp(v);
	if (u == v) return 0;
	if (sz[u] > sz[v]) swap(u, v);
	op.pb({u, v, sz[u], sz[v]});
	p[u] = v;
	sz[v] += sz[u];
	sz_comp--;
	return 1;
}

void go_back() {
	operation opp = op[op.size() - 1];
	int u = opp.u, v = opp.v, sz_u = opp.sz_u, sz_v = opp.sz_v;
	p[u] = u; p[v] = v; sz[u] = sz_u; sz[v] = sz_v;
	sz_comp++;
	op.pop_back();
}

vector <int> simulateCollapse(int n, vector <int> t, vector <int> x, vector <int> y, vector <int> w, vector <int> p) {
	int c = t.size(), q = w.size(), m = 0;
  if (c > 5005 || q > 5005 || n > 5005)
    	return {};
	vector <query> qu; qu.clear();
	for (int i = 0; i < q; i++) {
		qu.pb({w[i], p[i], i});
	}
	sort(qu.begin(), qu.end(), cmpquery);
	vector <int> refer, state, vis; refer.assign(c, 0);
	vector <pair<int, int>> edges; edges.clear();
	map <pair<int, int>, int> edge_id; edge_id.clear();
	for (int i = 0; i < c; i++) {
		if (x[i] > y[i]) swap(x[i], y[i]);
		if (!edge_id.count({x[i], y[i]})) edge_id[{x[i], y[i]}] = m++, edges.pb({x[i], y[i]});
		refer[i] = edge_id[{x[i], y[i]}];
	}
	state.assign(m, 0);
	vector <vector<int>> min_v, max_v, qus_v; min_v.assign(n, {}); max_v.assign(n, {}); qus_v.assign(n, {});
	vector <int> ans; ans.assign(q, 0);
	int curblock = 0, prv = -1;
	// for (int i = 0; i < m; i++) {
	// 	cout << i << " " << edges[i].fi << " " << edges[i].se << endl;
	// }
	// for (int i = 0; i < c; i++) {
	// 	cout << t[i] << " " << x[i] << " " << y[i] << " " << refer[i] << endl;
	// }
	// for (int i = 0; i < q; i++)
	// 	cout << qu[i].plan_day << " " << qu[i].collapse_town << " " << qu[i].id << endl;
	// cout << endl;
	while (true) {
		int l = curblock * blocksz, r = min(l + blocksz - 1, q - 1);
		vis.assign(m, 0);
		if (l >= q) break;
		for (int i = 0; i < n; i++) min_v[i].clear(), max_v[i].clear(), qus_v[i].clear();
		for (int i = l; i <= r; i++) {
			vis[refer[qu[i].plan_day]] = 1;
			qus_v[qu[i].collapse_town].pb(i);
		}
		for (int i = 0; i < m; i++) {
			if (state[i] && !vis[i]) {
				min_v[edges[i].fi].pb(i);
				max_v[edges[i].se].pb(i);
			}
		}
		make_set(n);
		for (int i = 0; i <= n - 2; i++) {
			for (int id : max_v[i])
				add(edges[id].fi, edges[id].se);
			for (int id : qus_v[i]) {
				int cnt_op = 0;
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				for (int j = prv + 1; j <= qu[r].plan_day; j++) {
					if (state[refer[j]] && edges[refer[j]].se <= i)
						cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
				}
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				ans[qu[id].id] += sz_comp - (n - i - 1);
				// cout << "left " << qu[id].id << " " << sz_comp - (n - i - 1) << endl;
				while (cnt_op--) go_back();
			}
		}
		make_set(n);
		for (int i = n - 1; i >= 1; i--) {
			for (int id : min_v[i])
				add(edges[id].fi, edges[id].se);
			for (int id : qus_v[i - 1]) {
				int cnt_op = 0;
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				for (int j = prv + 1; j <= qu[r].plan_day; j++) {
					if (state[refer[j]] && i <= edges[refer[j]].fi)
						cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
				}
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				ans[qu[id].id] += sz_comp - i;
				// cout << "rt " << qu[id].id << " " << sz_comp - i << endl;
				while (cnt_op--) go_back();
			}
		}
		for (int j = prv + 1; j <= qu[r].plan_day; j++) state[refer[j]] ^= 1;
		prv = qu[r].plan_day;
		curblock++;
	}
	return ans;
}

Compilation message

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:56:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |   if (c > 5005 || q > 5005 || n > 5005)
      |   ^~
collapse.cpp:58:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   58 |  vector <query> qu; qu.clear();
      |  ^~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 896 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 7 ms 620 KB Output is correct
5 Correct 470 ms 800 KB Output is correct
6 Correct 391 ms 1388 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 5 ms 1004 KB Output is correct
9 Correct 234 ms 1516 KB Output is correct
10 Correct 389 ms 1644 KB Output is correct
11 Correct 496 ms 1900 KB Output is correct
12 Correct 488 ms 1900 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 1900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 896 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 7 ms 620 KB Output is correct
5 Correct 470 ms 800 KB Output is correct
6 Correct 391 ms 1388 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 5 ms 1004 KB Output is correct
9 Correct 234 ms 1516 KB Output is correct
10 Correct 389 ms 1644 KB Output is correct
11 Correct 496 ms 1900 KB Output is correct
12 Correct 488 ms 1900 KB Output is correct
13 Incorrect 18 ms 1900 KB Output isn't correct
14 Halted 0 ms 0 KB -