oj.uz

Submission #547782

# Submission time Handle Problem Language Result Execution time Memory
547782 2022-04-11T18:12:29 Z blue Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 4548 KB 
#include "collapse.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int bs = 250;





vi simulateCollapse(int N, vi T, vi X, vi Y, vi W, vi P)
{	
	int C = sz(T);

	int Q = sz(W);

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

	vi res(Q);

	for(int q = 0; q < Q; q++)
	{
		set<pii> edges;
		for(int i = 0; i <= W[q]; i++)
		{
			if(X[i] <= P[q] && P[q]+1 <= Y[i]) continue;

			if(T[i] == 0)
				edges.insert({X[i], Y[i]});
			else
				edges.erase({X[i], Y[i]});
		}

		vi edge[N];
		for(auto& z : edges)
		{
			edge[z.first].push_back(z.second);
			edge[z.second].push_back(z.first);
		}

		int comps = 0;

		vi vis(N, 0);

		queue<int> tbv;

		for(int i = 0; i < N; i++)
		{
			if(vis[i]) continue;

			comps++;
			vis[i] = 1;

			tbv.push(i);
			while(!tbv.empty())
			{
				int u = tbv.front();
				tbv.pop();

				for(int v : edge[u])
				{
					if(vis[v]) continue;
					tbv.push(v);
					vis[v] = 1;
				}
			}
		}

		res[q] = comps;

		// cout << comps << '\n';
	}

	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 492 KB Output is correct
2 Correct 3 ms 312 KB Output is correct
3 Correct 9 ms 420 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 638 ms 556 KB Output is correct
6 Correct 1800 ms 896 KB Output is correct
7 Correct 219 ms 548 KB Output is correct
8 Correct 217 ms 588 KB Output is correct
9 Correct 888 ms 752 KB Output is correct
10 Correct 1454 ms 936 KB Output is correct
11 Correct 2873 ms 1128 KB Output is correct
12 Correct 2702 ms 1360 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2268 KB Output is correct
2 Correct 46 ms 2252 KB Output is correct
3 Execution timed out 15062 ms 4548 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2236 KB Output is correct
2 Correct 59 ms 2244 KB Output is correct
3 Correct 127 ms 2256 KB Output is correct
4 Correct 266 ms 2272 KB Output is correct
5 Correct 3677 ms 2300 KB Output is correct
6 Execution timed out 15040 ms 3536 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 492 KB Output is correct
2 Correct 3 ms 312 KB Output is correct
3 Correct 9 ms 420 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 638 ms 556 KB Output is correct
6 Correct 1800 ms 896 KB Output is correct
7 Correct 219 ms 548 KB Output is correct
8 Correct 217 ms 588 KB Output is correct
9 Correct 888 ms 752 KB Output is correct
10 Correct 1454 ms 936 KB Output is correct
11 Correct 2873 ms 1128 KB Output is correct
12 Correct 2702 ms 1360 KB Output is correct
13 Correct 29 ms 2268 KB Output is correct
14 Correct 46 ms 2252 KB Output is correct
15 Execution timed out 15062 ms 4548 KB Time limit exceeded
16 Halted 0 ms 0 KB -