oj.uz

Submission #1053188

# Submission time Handle Problem Language Result Execution time Memory
1053188 2024-08-11T09:32:16 Z tolbi Fountain Parks (IOI21_parks) C++17
15 / 100
 881 ms 218780 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);
struct DSU{
	vector<int> par;
	int tot;
	DSU(int n):tot(n){
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int node){
		if (par[node]==node) return node;
		return par[node]=find(par[node]);
	}
	bool merge(int a, int b){
		a=find(a);
		b=find(b);
		if (a!=b) tot--;
		else return false;
		par[a]=b;
		return true;
	}
};
int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();


	//subtasks 4..5
	DSU dsu(n);
	map<pair<int,int>,int> mp;
	for (int i = 0; i < n; ++i)
	{
		mp[{x[i],y[i]}]=i;
	}
	vector<int> u;
	vector<int> v;
	vector<int> xa(n-1,-1);
	vector<int> ya(n-1,-1);
	vector<set<pair<int,int>>> arr;
	map<pair<int,int>,set<int>> qu;
	for (int i = 0; i < n; ++i)
	{
		if (mp.count({x[i]-2,y[i]})){
			if (dsu.merge(mp[{x[i]-2,y[i]}],i)){
				u.push_back(mp[{x[i]-2,y[i]}]);
				v.push_back(i);
				arr.push_back(set<pair<int,int>>());
				arr.back().insert({x[i]-1,y[i]-1});
				arr.back().insert({x[i]-1,y[i]+1});
				qu[{x[i]-1,y[i]-1}].insert((int)u.size()-1);
				qu[{x[i]-1,y[i]+1}].insert((int)u.size()-1);
			}
		}
		if (mp.count({x[i],y[i]-2})){
			if (dsu.merge(mp[{x[i],y[i]-2}],i)){
				u.push_back(mp[{x[i],y[i]-2}]);
				v.push_back(i);
				arr.push_back(set<pair<int,int>>());
				arr.back().insert({x[i]-1,y[i]-1});
				arr.back().insert({x[i]+1,y[i]-1});
				qu[{x[i]-1,y[i]-1}].insert((int)u.size()-1);
				qu[{x[i]+1,y[i]-1}].insert((int)u.size()-1);
			}
		}
	}
	if (dsu.tot!=1) return 0;
	vector<pair<int,int>> iki;
	queue<pair<int,int>> que;
	int kal = n-1;
	for (auto it : qu){
		if (it.second.size()==1) que.push(it.first);
		else iki.push_back(it.first);
	}
	set<pair<int,int>> lmao;
	while (kal>0){
		if (!que.size()){
			while (iki.size() && qu[iki.back()].size()<2) iki.pop_back();
			if (iki.size()){
				int it = *qu[iki.back()].begin();
				arr[it].erase(iki.back());
				qu[iki.back()].erase(it);
				que.push(iki.back());
				iki.pop_back();
			}
			else return 0;
		}
		while (que.size() && (qu[que.front()].size()<1 || lmao.find(que.front())!=lmao.end())) que.pop();
		pair<int,int> pr = que.front();
		que.pop();
		int it = *qu[pr].begin();
		if (xa[it]!=-1) continue;
		kal--;
		lmao.insert(pr);
		xa[it]=pr.first, ya[it]=pr.second;
		for (auto it2 : arr[it]){
			if (qu[it2].find(it)!=qu[it2].end()) qu[it2].erase(it);
			if (qu[it2].size()==1) {
				que.push(it2);
			}
		}
		while (arr[it].size()) arr[it].erase(arr[it].begin());
	}
	build(u,v,xa,ya);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 373 ms 57440 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 124 ms 30992 KB Output is correct
12 Correct 27 ms 8724 KB Output is correct
13 Correct 47 ms 24064 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 319 ms 56996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 373 ms 57440 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 124 ms 30992 KB Output is correct
12 Correct 27 ms 8724 KB Output is correct
13 Correct 47 ms 24064 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 319 ms 56996 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 881 ms 97596 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 3 ms 860 KB Output is correct
26 Correct 3 ms 1628 KB Output is correct
27 Correct 5 ms 2140 KB Output is correct
28 Correct 262 ms 40744 KB Output is correct
29 Correct 427 ms 58364 KB Output is correct
30 Correct 622 ms 78292 KB Output is correct
31 Correct 857 ms 98472 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 1116 KB Output is correct
44 Correct 4 ms 1628 KB Output is correct
45 Correct 349 ms 52368 KB Output is correct
46 Correct 545 ms 74476 KB Output is correct
47 Correct 566 ms 75248 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 373 ms 57440 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 124 ms 30992 KB Output is correct
12 Correct 27 ms 8724 KB Output is correct
13 Correct 47 ms 24064 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 319 ms 56996 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 881 ms 97596 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 3 ms 860 KB Output is correct
26 Correct 3 ms 1628 KB Output is correct
27 Correct 5 ms 2140 KB Output is correct
28 Correct 262 ms 40744 KB Output is correct
29 Correct 427 ms 58364 KB Output is correct
30 Correct 622 ms 78292 KB Output is correct
31 Correct 857 ms 98472 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 1116 KB Output is correct
44 Correct 4 ms 1628 KB Output is correct
45 Correct 349 ms 52368 KB Output is correct
46 Correct 545 ms 74476 KB Output is correct
47 Correct 566 ms 75248 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Runtime error 774 ms 183284 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 373 ms 57440 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 124 ms 30992 KB Output is correct
12 Correct 27 ms 8724 KB Output is correct
13 Correct 47 ms 24064 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 319 ms 56996 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 682 ms 94864 KB Output is correct
21 Correct 755 ms 95988 KB Output is correct
22 Correct 712 ms 95440 KB Output is correct
23 Correct 655 ms 96660 KB Output is correct
24 Correct 135 ms 18260 KB Output is correct
25 Correct 550 ms 104536 KB Output is correct
26 Correct 580 ms 104944 KB Output is correct
27 Correct 867 ms 114156 KB Output is correct
28 Correct 861 ms 115188 KB Output is correct
29 Correct 848 ms 112248 KB Output is correct
30 Correct 827 ms 113764 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Incorrect 35 ms 7248 KB Tree (a[0], b[0]) = (185827, 20867) is not adjacent to edge between u[0]=8570 @(185790, 20626) and v[0]=0 @(185792, 20626)
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 373 ms 57440 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 124 ms 30992 KB Output is correct
12 Correct 27 ms 8724 KB Output is correct
13 Correct 47 ms 24064 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 319 ms 56996 KB Output is correct
17 Correct 818 ms 114272 KB Output is correct
18 Runtime error 703 ms 218780 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 373 ms 57440 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 124 ms 30992 KB Output is correct
12 Correct 27 ms 8724 KB Output is correct
13 Correct 47 ms 24064 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 319 ms 56996 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 881 ms 97596 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 3 ms 860 KB Output is correct
26 Correct 3 ms 1628 KB Output is correct
27 Correct 5 ms 2140 KB Output is correct
28 Correct 262 ms 40744 KB Output is correct
29 Correct 427 ms 58364 KB Output is correct
30 Correct 622 ms 78292 KB Output is correct
31 Correct 857 ms 98472 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 1116 KB Output is correct
44 Correct 4 ms 1628 KB Output is correct
45 Correct 349 ms 52368 KB Output is correct
46 Correct 545 ms 74476 KB Output is correct
47 Correct 566 ms 75248 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Runtime error 774 ms 183284 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -