oj.uz

Submission #1054490

# Submission time Handle Problem Language Result Execution time Memory
1054490 2024-08-12T10:16:01 Z aymanrs Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 9840 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int n, set<int> g[], bool v[], int p){
	v[n]=true;
	for(int j : g[n]){
		if(v[j]) continue;
		if(min(n,j) <= p && max(n,j) > p) continue;
		dfs(j, g, v, p);
	}
}
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
) {
	int q = W.size();
	vector<int> ans(q);
	int o[q];
	for(int i = 0;i < q;i++) o[i]=i;
	sort(o, o+q, [&W](int a, int b){return W[a]<W[b];});
	int tim = 0;
	set<int> g[N];
	bool v[N];
	for(int _ = 0;_ < q;_++){
		int qi = o[_];
		int t = W[qi];
		while(tim <= t){
			if(T[tim]){
				g[X[tim]].erase(Y[tim]);
				g[Y[tim]].erase(X[tim]);
			} else {
				g[X[tim]].insert(Y[tim]);
				g[Y[tim]].insert(X[tim]);
			}
			tim++;
		}
		ans[qi] = 0;
		fill(v,v+N,false);
		for(int i = 0;i < N;i++) {
			if(!v[i]){
				ans[qi]++;
				dfs(i, g, v, P[qi]);
			}
		}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 704 KB Output is correct
6 Correct 171 ms 1112 KB Output is correct
7 Correct 80 ms 808 KB Output is correct
8 Correct 76 ms 796 KB Output is correct
9 Correct 89 ms 984 KB Output is correct
10 Correct 110 ms 1028 KB Output is correct
11 Correct 443 ms 1336 KB Output is correct
12 Correct 341 ms 1600 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3164 KB Output is correct
2 Correct 16 ms 3008 KB Output is correct
3 Correct 88 ms 6496 KB Output is correct
4 Correct 30 ms 3132 KB Output is correct
5 Correct 163 ms 6976 KB Output is correct
6 Correct 2963 ms 3968 KB Output is correct
7 Execution timed out 15032 ms 9840 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3164 KB Output is correct
2 Correct 25 ms 3132 KB Output is correct
3 Correct 23 ms 3164 KB Output is correct
4 Correct 30 ms 3272 KB Output is correct
5 Correct 244 ms 3484 KB Output is correct
6 Correct 3383 ms 4024 KB Output is correct
7 Execution timed out 15032 ms 8592 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 704 KB Output is correct
6 Correct 171 ms 1112 KB Output is correct
7 Correct 80 ms 808 KB Output is correct
8 Correct 76 ms 796 KB Output is correct
9 Correct 89 ms 984 KB Output is correct
10 Correct 110 ms 1028 KB Output is correct
11 Correct 443 ms 1336 KB Output is correct
12 Correct 341 ms 1600 KB Output is correct
13 Correct 14 ms 3164 KB Output is correct
14 Correct 16 ms 3008 KB Output is correct
15 Correct 88 ms 6496 KB Output is correct
16 Correct 30 ms 3132 KB Output is correct
17 Correct 163 ms 6976 KB Output is correct
18 Correct 2963 ms 3968 KB Output is correct
19 Execution timed out 15032 ms 9840 KB Time limit exceeded
20 Halted 0 ms 0 KB -