oj.uz

Submission #363314

# Submission time Handle Problem Language Result Execution time Memory
363314 2021-02-05T13:46:46 Z r57shell Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 6124 KB 
#include "collapse.h"
#include <vector>
#include <set>

using namespace std;

const int MAXN = 1e5;

static int PP[MAXN][4];

int getp(int x)
{
	if (PP[x][0] == x)
		return x;
	return (PP[x][0] = getp(PP[x][0]));
}

void join(int a, int b)
{
	a = getp(a);
	b = getp(b);
	if (a == b)
		return;
	if (PP[a][1] < PP[b][1])
		swap(a, b);
	PP[b][0] = a;
	PP[a][1] += PP[b][1];
}

vector<int> simulateCollapse(
	int N,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P)
{
	for (int i = 0; i < X.size(); ++i)
		if (X[i] > Y[i])
			swap(X[i], Y[i]);
	vector<int> ans(W.size());
	vector<pair<int,int>> Q(W.size());
	for (int i = 0; i < W.size(); ++i)
		Q[i] = pair<int,int>(W[i], i);
	for (int z = 0; z < W.size(); ++z)
	{
		for (int j = 0; j < N; ++j)
		{
			PP[j][0] = j;
			PP[j][1] = 1;
			PP[j][2] = 0;
		}
		int i = Q[z].second;
		int cut = P[i];
		//printf("$%d %d$\n", i, cut);
		set<pair<int,int>> edges;
		for (int j = 0; j <= W[i]; ++j)
		{
			//printf("|%d %d %d|\n", T[j], X[j], Y[j]);
			if (T[j] == 0)
				edges.insert(pair<int,int>(X[j], Y[j]));
			else
				edges.erase(pair<int,int>(X[j], Y[j]));
		}
		set<pair<int,int>>::iterator f;
		for (f = edges.begin(); f != edges.end(); ++f)
		{
			//printf("((%d %d))\n", f->first, f->second);
			if (f->first > cut || f->second <= cut)
			{
				join(f->first, f->second);
				//printf("(%d %d)", f->first, f->second);
			}
		}
		int res = 0;
		for (int j = 0; j < N; ++j)
		{
			int a = getp(j);
			if (PP[a][2] == 0)
			{
				PP[a][2] = 1;
				//printf("!%d!",a);
				++res;
			}
		}
		//printf("=(%d)%d\n", i,res);
		ans[i] = res;
	}
	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:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < X.size(); ++i)
      |                  ~~^~~~~~~~~~
collapse.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < W.size(); ++i)
      |                  ~~^~~~~~~~~~
collapse.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int z = 0; z < W.size(); ++z)
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 768 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 9 ms 492 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 990 ms 748 KB Output is correct
6 Correct 2424 ms 1004 KB Output is correct
7 Correct 78 ms 620 KB Output is correct
8 Correct 81 ms 620 KB Output is correct
9 Correct 1020 ms 876 KB Output is correct
10 Correct 1799 ms 896 KB Output is correct
11 Correct 2771 ms 1132 KB Output is correct
12 Correct 2741 ms 1036 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3436 KB Output is correct
2 Correct 46 ms 3456 KB Output is correct
3 Execution timed out 15046 ms 6124 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3436 KB Output is correct
2 Correct 48 ms 3436 KB Output is correct
3 Correct 96 ms 3436 KB Output is correct
4 Correct 192 ms 3564 KB Output is correct
5 Correct 2959 ms 3820 KB Output is correct
6 Execution timed out 15091 ms 4204 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 768 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 9 ms 492 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 990 ms 748 KB Output is correct
6 Correct 2424 ms 1004 KB Output is correct
7 Correct 78 ms 620 KB Output is correct
8 Correct 81 ms 620 KB Output is correct
9 Correct 1020 ms 876 KB Output is correct
10 Correct 1799 ms 896 KB Output is correct
11 Correct 2771 ms 1132 KB Output is correct
12 Correct 2741 ms 1036 KB Output is correct
13 Correct 31 ms 3436 KB Output is correct
14 Correct 46 ms 3456 KB Output is correct
15 Execution timed out 15046 ms 6124 KB Time limit exceeded
16 Halted 0 ms 0 KB -