oj.uz

답안 #603410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603410 2022-07-24T06:23:35 Z 장태환(#8428) Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 155108 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#include <assert.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)
	{
		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)
			{
				int v= u(q1[j], q2[j]);
				rbc += v;
				p -= v;
			}
		}
		ans[s] = p;
		T:
		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();
		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:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (i = 0; i < T.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 < P.size(); i++)
      |              ~~^~~~~~~~~~
collapse.cpp:127:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for (i = 0; i < T.size(); i += bc)
      |              ~~^~~~~~~~~~
collapse.cpp:148: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]
  148 |    for (k = 0; k < q[j].size(); k++)
      |                ~~^~~~~~~~~~~~~
collapse.cpp:154: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]
  154 |   for (j = 0; j < ccq.size(); j++)
      |               ~~^~~~~~~~~~~~
collapse.cpp:159: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]
  159 |   for (treeN = 1; treeN < cq.size(); treeN *= 2);
      |                   ~~~~~~^~~~~~~~~~~
collapse.cpp:164:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |   for (j = 0; j < T.size(); j++)
      |               ~~^~~~~~~~~~
collapse.cpp:176: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]
  176 |   for (j = 0; j < cq.size(); j++)
      |               ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 27732 KB Output is correct
2 Incorrect 15 ms 27648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 33728 KB Output is correct
2 Correct 63 ms 33768 KB Output is correct
3 Correct 60 ms 34052 KB Output is correct
4 Correct 71 ms 34288 KB Output is correct
5 Correct 653 ms 34148 KB Output is correct
6 Correct 624 ms 33260 KB Output is correct
7 Correct 4333 ms 86468 KB Output is correct
8 Correct 8662 ms 119876 KB Output is correct
9 Correct 57 ms 35348 KB Output is correct
10 Correct 675 ms 36012 KB Output is correct
11 Correct 7756 ms 155108 KB Output is correct
12 Execution timed out 15046 ms 96992 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 27732 KB Output is correct
2 Incorrect 15 ms 27648 KB Output isn't correct
3 Halted 0 ms 0 KB -