답안 #603394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603394 2022-07-24T06:02:06 Z 장태환(#8428) Collapse (JOI18_collapse) C++17
0 / 100
76 ms 60440 KB
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int uf[100100];
int siz[100100];
int rb[10000100][2];
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] += siz[n];
	rb[c][0] = n;
	rb[c][1] = n;
	c++;
	uf[n] = uf[m];
	return 1;
}
int ans[100100];
int tgt[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)
	{
		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)
			{
				int v= u(q1[j], q2[j]);
				rbc += v;
				p -= v;
			}
		}
		ans[s] = p;
		p += rbc;
		while (rbc--)
		{
			c--;
			uf[rb[c][0]] = rb[c][1];
		}
		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][0]] = rb[c][1];
	}
}
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
) {
	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)
		{
			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 = 1000;
	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();
		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++)
			{
				cq.push_back({q[j][k].first,j});
				ai[cq.size() - 1] = q[j][k].second;
			}
		}
		for (treeN = 1; treeN < cq.size(); treeN *= 2);
		for (j = 1; j < 2 * treeN; j++)
		{
			stree[j].clear();
		}
		sort(cq.begin(), cq.end());
		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])]];
		}

	}
	return rans;
}

Compilation message

collapse.cpp: In function 'void odc(int, int, int, int)':
collapse.cpp:45: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]
   45 |  for (j = 0; j < stree[i].size(); j++)
      |              ~~^~~~~~~~~~~~~~~~~
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:106:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for (i = 0; i < T.size(); i++)
      |              ~~^~~~~~~~~~
collapse.cpp:117:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for (i = 0; i < P.size(); i++)
      |              ~~^~~~~~~~~~
collapse.cpp:122:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (i = 0; i < T.size(); i += bc)
      |              ~~^~~~~~~~~~
collapse.cpp:142: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]
  142 |    for (k = 0; k < q[j].size(); k++)
      |                ~~^~~~~~~~~~~~~
collapse.cpp:148: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]
  148 |   for (treeN = 1; treeN < cq.size(); treeN *= 2);
      |                   ~~~~~~^~~~~~~~~~~
collapse.cpp:154:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   for (j = 0; j < T.size(); j++)
      |               ~~^~~~~~~~~~
collapse.cpp:166: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]
  166 |   for (j = 0; j < cq.size(); j++)
      |               ~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 27724 KB Output is correct
2 Incorrect 19 ms 27588 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 60412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 68 ms 60440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 27724 KB Output is correct
2 Incorrect 19 ms 27588 KB Output isn't correct
3 Halted 0 ms 0 KB -