oj.uz

Submission #102201

# Submission time Handle Problem Language Result Execution time Memory
102201 2019-03-23T12:02:11 Z Minnakhmetov Collapse (JOI18_collapse) C++14
100 / 100
 4342 ms 20788 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

#include "collapse.h"
using namespace std;

struct E {
	int x, y, i;
	bool operator < (const E &oth) const {
		return x < oth.x;
	}
};

struct Q {
	int t, type, i, x;
	bool operator < (const Q &oth) const {
		return t == oth.t ? type : t < oth.t;
	}
};

const int N = 1e5 + 5, Z = 350;
bool isOn[N], usedv[N], usede[N];
int par[N];
vector<E> edges, se1, se2;
map<pair<int, int>, int> mp_e;
vector<int> ans;
map<int, vector<pair<int, int>>> mp;
int n, m;

#define all(aaa) aaa.begin(), aaa.end()

int findSet(int v) {
	return par[v] == v ? v : par[v] = findSet(par[v]);
}

bool un(int x, int y) {
	x = findSet(x);
	y = findSet(y);
	if (x == y)
		return false;
	if (usedv[y])
		swap(x, y);
	par[y] = x;
	return true;
}

void solve(vector<Q> qr) {
	fill(usedv, usedv + N, false);
	fill(usede, usede + N, false);
	mp.clear();

	vector<Q> s;
	vector<E> ve;
	vector<int> vtx;
	
	for (Q q : qr) {
		if (q.type) {
			usede[q.i] = usedv[edges[q.i].x] = 
				usedv[edges[q.i].y] = 1;
		}
		else {
			s.push_back(q);
		}
	}

	for (int i = 0; i < n; i++) {
		if (usedv[i]) {
			vtx.push_back(i);
		}
	}

	for (int i = 0; i < m; i++) {
		if (usede[i]) {
			ve.push_back(edges[i]);
		}
	}

	sort(all(s), [](Q &a, Q &b) {
		return a.x < b.x;
	});

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
		while (j < se1.size() && se1[j].x <= s[i].x) {
			if (!usede[se1[j].i] && isOn[se1[j].i])
				r += un(se1[j].x, se1[j].y);
			j++;
		}
		ans[s[i].i] -= r;
		for (int k : vtx) {
			if (k <= s[i].x)
				mp[s[i].i].push_back({ k, findSet(k) });
		}
	}

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	for (int i = s.size() - 1, j = 0, r = 0; i >= 0; i--) {
		while (j < se2.size() && se2[j].x > s[i].x) {
			if (!usede[se2[j].i] && isOn[se2[j].i])
				r += un(se2[j].x, se2[j].y);
			j++;
		}
		ans[s[i].i] -= r;
		for (int k : vtx) {
			if (k > s[i].x)
				mp[s[i].i].push_back({ k, findSet(k) });
		}
	}

	for (Q q : qr) {
		if (q.type) {
			isOn[q.i] ^= 1;
		}
		else {
			for (auto p : mp[q.i])
				par[p.first] = p.second;
			for (E e : ve) {
				if (isOn[e.i] &&
					(e.x <= q.x || e.y > q.x)) {
					ans[q.i] -= un(e.x, e.y);
				}
			}
		}
	}
}

vector<int> simulateCollapse(
	int _n,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
	n = _n;
	m = T.size();
	
	int q = W.size();
	vector<Q> v;

	for (int i = 0; i < m; i++) {
		if (X[i] < Y[i])
			swap(X[i], Y[i]);

		int num;
		if (!mp_e.count({ X[i], Y[i] })) {
			num = edges.size();
			edges.push_back({ X[i], Y[i], num });
			mp_e[{X[i], Y[i]}] = num;
			se1.push_back({ X[i], Y[i], num });
			se2.push_back({ Y[i], X[i], num });
		}
		else {
			num = mp_e[{X[i], Y[i]}];
		}
		
		v.push_back({ i, 1, num });
	}

	sort(all(se1));
	sort(all(se2));
	reverse(all(se2));

	ans.resize(q, _n);

	for (int i = 0; i < q; i++) {
		v.push_back({ W[i], 0, i, P[i] });
	}

	sort(all(v));

	for (int i = 0; i < v.size(); i++) {
		if (i % Z == 0) {
			solve(vector<Q>(v.begin() + i, v.begin() + min((int)v.size(), i + Z)));
		}
	}

	return ans;
}

Compilation message

collapse.cpp: In function 'void solve(std::vector<Q>)':
collapse.cpp:119:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
                                ~~^~~~~~~~~~
collapse.cpp:120:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < se1.size() && se1[j].x <= s[i].x) {
          ~~^~~~~~~~~~~~
collapse.cpp:137:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < se2.size() && se2[j].x > s[i].x) {
          ~~^~~~~~~~~~~~
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:211:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1020 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Correct 13 ms 852 KB Output is correct
5 Correct 23 ms 1176 KB Output is correct
6 Correct 36 ms 1792 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 9 ms 896 KB Output is correct
9 Correct 48 ms 1852 KB Output is correct
10 Correct 64 ms 1840 KB Output is correct
11 Correct 73 ms 2480 KB Output is correct
12 Correct 55 ms 2012 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 4540 KB Output is correct
2 Correct 111 ms 4588 KB Output is correct
3 Correct 383 ms 10116 KB Output is correct
4 Correct 113 ms 4976 KB Output is correct
5 Correct 656 ms 10760 KB Output is correct
6 Correct 257 ms 6124 KB Output is correct
7 Correct 1398 ms 20116 KB Output is correct
8 Correct 1000 ms 15504 KB Output is correct
9 Correct 173 ms 5608 KB Output is correct
10 Correct 166 ms 5612 KB Output is correct
11 Correct 253 ms 6028 KB Output is correct
12 Correct 1322 ms 15736 KB Output is correct
13 Correct 1338 ms 17280 KB Output is correct
14 Correct 1828 ms 20616 KB Output is correct
15 Correct 1618 ms 20744 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 4516 KB Output is correct
2 Correct 86 ms 4584 KB Output is correct
3 Correct 99 ms 4844 KB Output is correct
4 Correct 108 ms 4972 KB Output is correct
5 Correct 149 ms 5108 KB Output is correct
6 Correct 324 ms 6176 KB Output is correct
7 Correct 1792 ms 17308 KB Output is correct
8 Correct 3094 ms 20360 KB Output is correct
9 Correct 186 ms 5740 KB Output is correct
10 Correct 294 ms 6028 KB Output is correct
11 Correct 3227 ms 20596 KB Output is correct
12 Correct 4342 ms 20752 KB Output is correct
13 Correct 3616 ms 20608 KB Output is correct
14 Correct 4161 ms 20616 KB Output is correct
15 Correct 3178 ms 20360 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1020 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 10 ms 896 KB Output is correct
4 Correct 13 ms 852 KB Output is correct
5 Correct 23 ms 1176 KB Output is correct
6 Correct 36 ms 1792 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 9 ms 896 KB Output is correct
9 Correct 48 ms 1852 KB Output is correct
10 Correct 64 ms 1840 KB Output is correct
11 Correct 73 ms 2480 KB Output is correct
12 Correct 55 ms 2012 KB Output is correct
13 Correct 91 ms 4540 KB Output is correct
14 Correct 111 ms 4588 KB Output is correct
15 Correct 383 ms 10116 KB Output is correct
16 Correct 113 ms 4976 KB Output is correct
17 Correct 656 ms 10760 KB Output is correct
18 Correct 257 ms 6124 KB Output is correct
19 Correct 1398 ms 20116 KB Output is correct
20 Correct 1000 ms 15504 KB Output is correct
21 Correct 173 ms 5608 KB Output is correct
22 Correct 166 ms 5612 KB Output is correct
23 Correct 253 ms 6028 KB Output is correct
24 Correct 1322 ms 15736 KB Output is correct
25 Correct 1338 ms 17280 KB Output is correct
26 Correct 1828 ms 20616 KB Output is correct
27 Correct 1618 ms 20744 KB Output is correct
28 Correct 89 ms 4516 KB Output is correct
29 Correct 86 ms 4584 KB Output is correct
30 Correct 99 ms 4844 KB Output is correct
31 Correct 108 ms 4972 KB Output is correct
32 Correct 149 ms 5108 KB Output is correct
33 Correct 324 ms 6176 KB Output is correct
34 Correct 1792 ms 17308 KB Output is correct
35 Correct 3094 ms 20360 KB Output is correct
36 Correct 186 ms 5740 KB Output is correct
37 Correct 294 ms 6028 KB Output is correct
38 Correct 3227 ms 20596 KB Output is correct
39 Correct 4342 ms 20752 KB Output is correct
40 Correct 3616 ms 20608 KB Output is correct
41 Correct 4161 ms 20616 KB Output is correct
42 Correct 3178 ms 20360 KB Output is correct
43 Correct 1148 ms 15060 KB Output is correct
44 Correct 2237 ms 20216 KB Output is correct
45 Correct 1345 ms 15316 KB Output is correct
46 Correct 2957 ms 20260 KB Output is correct
47 Correct 188 ms 5640 KB Output is correct
48 Correct 184 ms 5740 KB Output is correct
49 Correct 274 ms 6128 KB Output is correct
50 Correct 648 ms 7912 KB Output is correct
51 Correct 1310 ms 15312 KB Output is correct
52 Correct 2115 ms 16808 KB Output is correct
53 Correct 1778 ms 15600 KB Output is correct
54 Correct 2836 ms 17768 KB Output is correct
55 Correct 2048 ms 17044 KB Output is correct
56 Correct 2714 ms 18288 KB Output is correct
57 Correct 3266 ms 19332 KB Output is correct
58 Correct 3804 ms 19860 KB Output is correct
59 Correct 3305 ms 20392 KB Output is correct
60 Correct 4232 ms 20788 KB Output is correct