oj.uz

Submission #603423

# Submission time Handle Problem Language Result Execution time Memory
603423 2022-07-24T06:41:12 Z 장태환(#8428) Collapse (JOI18_collapse) C++17
100 / 100
 6250 ms 134212 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
int uf[100100];
int siz[100100];
int rb[400000];
int c;
vector<pair<int, int>>stree[1 << 20];
int q1[100100];
int q2[100100];
int ty[100100];
vector<pair<int, int>>cq;
vector<pair<int, int>>q[100100];
int treeN;
int sc, ec;
int f(int n)
{
	while (n != uf[n])
	{
		n = uf[n];
	}
	return n;
}
int u(int n, int m)
{
	n = f(n);
	m = f(m);
	if (n == m)
		return 0;
	if (siz[n] > siz[m])
		swap(n, m);
	siz[m] = max(siz[n],siz[m]+1);
	rb[c] = n;
	c++;
	uf[n] = uf[m];
	return 1;
}
int ans[100100];
int tgt[100100];
int ert[100100];
void odc(int p, int s = 0, int e = treeN - 1, int i = 1)
{
	int rbc = 0;
	int j;
	for (j = 0; j < stree[i].size(); j++)
	{
		int v = u(stree[i][j].first, stree[i][j].second);
		p -= v;
		rbc += v;
	}
	if (s == e)
	{
		if (cq.size() <= s)
			goto T;
		for (j = sc; j <= ec; j++)
		{
			if (ty[j] != (j <= cq[s].second) && ((q1[j] <= cq[s].first) ^ (q2[j] > cq[s].first)) && tgt[j] <= cq[s].second && ert[j] > cq[s].second)
			{
				int v = u(q1[j], q2[j]);
				rbc += v;
				p -= v;
			}
		}
		ans[s] = p;
	T:
		p += rbc;
		while (rbc--)
		{
			c--;
			uf[rb[c]] = rb[c];
		}
		return;
	}

	odc(p, s, (s + e) / 2, i * 2);
	odc(p, (s + e) / 2 + 1, e, i * 2 + 1);
	p += rbc;
	while (rbc--)
	{
		c--;
		uf[rb[c]] = rb[c];
	}
}
void pu(int qs, int qe, pair<int, int>va, int s = 0, int e = treeN - 1, int i = 1)
{
	if (qs > qe || s > qe || qs > e)
		return;
	if (qs <= s && e <= qe)
	{
		stree[i].push_back(va);
		return;
	}
	pu(qs, qe, va, s, (s + e) / 2, i * 2);
	pu(qs, qe, va, (s + e) / 2 + 1, e, i * 2 + 1);
}
int ct[100100];
int rct[100100];
int ai[100100];
map<pair<int, int>, int>r;
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	memset(ert, 10, sizeof(ert));
	vector<int>rans(W.size());
	int i;
	for (i = 0; i < T.size(); i++)
	{
		ty[i] = T[i];
		q1[i] = min(X[i], Y[i]);
		q2[i] = max(X[i], Y[i]);
		if (ty[i] == 1)
		{
			ert[r[make_pair(q1[i], q2[i])]] = i;
			tgt[i] = r[make_pair(q1[i], q2[i])];
		}
		r[make_pair(q1[i], q2[i])] = i;
	}
	for (i = 0; i < P.size(); i++)
	{
		q[W[i]].push_back({ P[i],i });
	}
	int bc =2000;
	for (i = 0; i < T.size(); i += bc)
	{
		sc = i;
		ec = min(i + bc - 1, (int)T.size() - 1);

		int j;

		for (j = 0; j < N; j++)
		{
			uf[j] = j;
			siz[j] = 1;
		}
		cq.clear();
		vector<pair<pair<int, int>, int>>ccq;
		for (j = sc; j <= ec; j++)
		{
			if (ty[j] == 1)
			{
				ct[r[make_pair(q1[j], q2[j])]] = 0;
			}
			int k;
			for (k = 0; k < q[j].size(); k++)
			{
				ccq.push_back({ {q[j][k].first,j},q[j][k].second });
			}
		}
		sort(ccq.begin(), ccq.end());
		for (j = 0; j < ccq.size(); j++)
		{
			cq.push_back(ccq[j].first);
			ai[j] = ccq[j].second;
		}
		for (treeN = 1; treeN < cq.size(); treeN *= 2);
		for (j = 1; j < 2 * treeN; j++)
		{
			stree[j].clear();
		}
		for (j = 0; j < T.size(); j++)
		{
			if (ct[r[make_pair(q1[j], q2[j])]])
			{
				int sp = lower_bound(cq.begin(), cq.end(), make_pair(q1[j], 0)) - cq.begin();
				int ep = lower_bound(cq.begin(), cq.end(), make_pair(q2[j], 0)) - cq.begin();
				pu(0, sp - 1, make_pair(q1[j], q2[j]));
				pu(ep, (int)cq.size() - 1, make_pair(q1[j], q2[j]));
			}
		}
		if (cq.size())
			odc(N);
		for (j = 0; j < cq.size(); j++)
		{
			rans[ai[j]] = ans[j];
		}
		for (j = sc; j <= ec; j++)
		{
			rct[r[make_pair(q1[j], q2[j])]] = !ty[j];
			ct[r[make_pair(q1[j], q2[j])]] = rct[r[make_pair(q1[j], q2[j])]];
		}
		assert(c == 0);

	}
	return rans;
}

Compilation message

collapse.cpp: In function 'void odc(int, int, int, int)':
collapse.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (j = 0; j < stree[i].size(); j++)
      |              ~~^~~~~~~~~~~~~~~~~
collapse.cpp:54:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   if (cq.size() <= s)
      |       ~~~~~~~~~~^~~~
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:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (i = 0; i < T.size(); i++)
      |              ~~^~~~~~~~~~
collapse.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for (i = 0; i < P.size(); i++)
      |              ~~^~~~~~~~~~
collapse.cpp:129:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for (i = 0; i < T.size(); i += bc)
      |              ~~^~~~~~~~~~
collapse.cpp:150:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |    for (k = 0; k < q[j].size(); k++)
      |                ~~^~~~~~~~~~~~~
collapse.cpp:156:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |   for (j = 0; j < ccq.size(); j++)
      |               ~~^~~~~~~~~~~~
collapse.cpp:161:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |   for (treeN = 1; treeN < cq.size(); treeN *= 2);
      |                   ~~~~~~^~~~~~~~~~~
collapse.cpp:166:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |   for (j = 0; j < T.size(); j++)
      |               ~~^~~~~~~~~~
collapse.cpp:178:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |   for (j = 0; j < cq.size(); j++)
      |               ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28244 KB Output is correct
2 Correct 16 ms 28064 KB Output is correct
3 Correct 17 ms 28116 KB Output is correct
4 Correct 18 ms 28084 KB Output is correct
5 Correct 52 ms 28216 KB Output is correct
6 Correct 85 ms 29224 KB Output is correct
7 Correct 17 ms 28128 KB Output is correct
8 Correct 16 ms 28112 KB Output is correct
9 Correct 61 ms 28444 KB Output is correct
10 Correct 124 ms 28524 KB Output is correct
11 Correct 97 ms 29180 KB Output is correct
12 Correct 89 ms 29268 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 34108 KB Output is correct
2 Correct 51 ms 34568 KB Output is correct
3 Correct 929 ms 36816 KB Output is correct
4 Correct 58 ms 34800 KB Output is correct
5 Correct 1456 ms 37708 KB Output is correct
6 Correct 882 ms 33636 KB Output is correct
7 Correct 2942 ms 45972 KB Output is correct
8 Correct 1797 ms 40772 KB Output is correct
9 Correct 56 ms 34980 KB Output is correct
10 Correct 64 ms 35080 KB Output is correct
11 Correct 631 ms 35824 KB Output is correct
12 Correct 1807 ms 41384 KB Output is correct
13 Correct 2998 ms 44032 KB Output is correct
14 Correct 3366 ms 46952 KB Output is correct
15 Correct 3074 ms 46920 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34244 KB Output is correct
2 Correct 55 ms 34280 KB Output is correct
3 Correct 63 ms 34508 KB Output is correct
4 Correct 72 ms 34652 KB Output is correct
5 Correct 284 ms 34576 KB Output is correct
6 Correct 1184 ms 33736 KB Output is correct
7 Correct 3537 ms 74996 KB Output is correct
8 Correct 5574 ms 96608 KB Output is correct
9 Correct 66 ms 34968 KB Output is correct
10 Correct 774 ms 35424 KB Output is correct
11 Correct 5350 ms 123908 KB Output is correct
12 Correct 6179 ms 97588 KB Output is correct
13 Correct 5797 ms 123124 KB Output is correct
14 Correct 6250 ms 106888 KB Output is correct
15 Correct 5470 ms 128632 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28244 KB Output is correct
2 Correct 16 ms 28064 KB Output is correct
3 Correct 17 ms 28116 KB Output is correct
4 Correct 18 ms 28084 KB Output is correct
5 Correct 52 ms 28216 KB Output is correct
6 Correct 85 ms 29224 KB Output is correct
7 Correct 17 ms 28128 KB Output is correct
8 Correct 16 ms 28112 KB Output is correct
9 Correct 61 ms 28444 KB Output is correct
10 Correct 124 ms 28524 KB Output is correct
11 Correct 97 ms 29180 KB Output is correct
12 Correct 89 ms 29268 KB Output is correct
13 Correct 45 ms 34108 KB Output is correct
14 Correct 51 ms 34568 KB Output is correct
15 Correct 929 ms 36816 KB Output is correct
16 Correct 58 ms 34800 KB Output is correct
17 Correct 1456 ms 37708 KB Output is correct
18 Correct 882 ms 33636 KB Output is correct
19 Correct 2942 ms 45972 KB Output is correct
20 Correct 1797 ms 40772 KB Output is correct
21 Correct 56 ms 34980 KB Output is correct
22 Correct 64 ms 35080 KB Output is correct
23 Correct 631 ms 35824 KB Output is correct
24 Correct 1807 ms 41384 KB Output is correct
25 Correct 2998 ms 44032 KB Output is correct
26 Correct 3366 ms 46952 KB Output is correct
27 Correct 3074 ms 46920 KB Output is correct
28 Correct 46 ms 34244 KB Output is correct
29 Correct 55 ms 34280 KB Output is correct
30 Correct 63 ms 34508 KB Output is correct
31 Correct 72 ms 34652 KB Output is correct
32 Correct 284 ms 34576 KB Output is correct
33 Correct 1184 ms 33736 KB Output is correct
34 Correct 3537 ms 74996 KB Output is correct
35 Correct 5574 ms 96608 KB Output is correct
36 Correct 66 ms 34968 KB Output is correct
37 Correct 774 ms 35424 KB Output is correct
38 Correct 5350 ms 123908 KB Output is correct
39 Correct 6179 ms 97588 KB Output is correct
40 Correct 5797 ms 123124 KB Output is correct
41 Correct 6250 ms 106888 KB Output is correct
42 Correct 5470 ms 128632 KB Output is correct
43 Correct 2129 ms 41520 KB Output is correct
44 Correct 5158 ms 100000 KB Output is correct
45 Correct 2281 ms 42196 KB Output is correct
46 Correct 5695 ms 99984 KB Output is correct
47 Correct 62 ms 35772 KB Output is correct
48 Correct 64 ms 35844 KB Output is correct
49 Correct 921 ms 36788 KB Output is correct
50 Correct 1706 ms 37132 KB Output is correct
51 Correct 2420 ms 43012 KB Output is correct
52 Correct 3778 ms 60040 KB Output is correct
53 Correct 3826 ms 70484 KB Output is correct
54 Correct 4594 ms 72748 KB Output is correct
55 Correct 4269 ms 88228 KB Output is correct
56 Correct 5040 ms 104776 KB Output is correct
57 Correct 5449 ms 111132 KB Output is correct
58 Correct 5812 ms 87196 KB Output is correct
59 Correct 5285 ms 134212 KB Output is correct
60 Correct 6103 ms 109060 KB Output is correct