oj.uz

Submission #831608

# Submission time Handle Problem Language Result Execution time Memory
831608 2023-08-20T11:14:51 Z andrey27_sm Fountain Parks (IOI21_parks) C++17
5 / 100
 245 ms 46376 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> cons[200001];
int mask_l[200001];
vector<int> u;
vector<int> v;
vector<int> a;
vector<int> b;
struct dsu{
	int sz = 0;
	vector<int> pr;
	int p(int v){
		if(pr[v] == v) return v;
		return pr[v] = p(pr[v]);
	}
	void un(int u,int v){
		u = p(u);
		v = p(v);
		if(u == v) return;
		pr[u] = v;
		sz++;
	}
} D;
struct edge{
	int x;
	int y;
	int type; // 0 - vert, 1 - hor;
	int a;
	int b;
};
int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	D.pr.resize(n);
	for (int i = 0; i < n; ++i)
	{
		D.pr[i] = i;
	}
	vector<edge> E;
	vector<pair<int,pair<int,int>>> x_d;
	vector<pair<int,pair<int,int>>> y_d;
	for (int i = 0; i < n; ++i)
	{
	 	x_d.push_back({x[i],{y[i],i}});
	 	y_d.push_back({y[i],{x[i],i}});
	} 
	sort(x_d.begin(), x_d.end());
	sort(y_d.begin(), y_d.end());
	for (int i = 1; i < n; ++i)
	{
		if(x_d[i].first == x_d[i-1].first and x_d[i].second.first-2 == x_d[i-1].second.first){
			E.push_back({x_d[i-1].first,x_d[i-1].second.first,0,x_d[i-1].second.second,x_d[i].second.second});
			D.un(x_d[i-1].second.second,x_d[i].second.second);
		}
	}
	for (int i = 1; i < n; ++i)
	{
		if(y_d[i].first == y_d[i-1].first and y_d[i].second.first-2 == y_d[i-1].second.first){
			E.push_back({y_d[i-1].second.first,y_d[i-1].first,1,y_d[i-1].second.second,y_d[i].second.second});
			D.un(y_d[i-1].second.second,y_d[i].second.second);
		}
	}
	if(D.sz != n-1) return 0;
	set<pair<int,int>> lines;
	set<pair<int,int>> points;
	sort(E.begin(),E.end(),[](auto a,auto b){
		if(a.x != b.x) return a.x < b.x;
		if(a.type != b.type) return a.type < b.type;
		return a.y < b.y;
	});
	for (int i = 0; i < E.size(); ++i)
	{
		if(E[i].type == 0) lines.insert({E[i].x,E[i].y});
	}
	for (int i = 0; i < E.size(); ++i)
	{
		//cout << E[i].x << " " << E[i].y << "   --\n";
		if(E[i].type == 0){
			if(points.count({E[i].x-1,E[i].y+1})){
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x+1);
				b.push_back(E[i].y+1);
				points.insert({E[i].x+1,E[i].y+1});
			}
			else{				
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x-1);
				b.push_back(E[i].y+1);
				points.insert({E[i].x-1,E[i].y+1});
			}
		}
		else{
			int top = 0;
			if(points.count({E[i].x+1,E[i].y-1})) top = 1;
			else if(points.count({E[i].x+1,E[i].y+1})) top = 2;
			if(top == 0 and lines.count({E[i].x+2,E[i].y})) top = 2;
			if(top == 0 and lines.count({E[i].x+2,E[i].y-2})) top = 1;
			if(top%2 == 0){
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x+1);
				b.push_back(E[i].y-1);
				points.insert({E[i].x+1,E[i].y-1});
			}
			else{				
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x+1);
				b.push_back(E[i].y+1);
				points.insert({E[i].x+1,E[i].y+1});
			}
		}
	}
	if(points.size() != n-1) return 0;
	build(u,v,a,b);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < E.size(); ++i)
      |                  ~~^~~~~~~~~~
parks.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for (int i = 0; i < E.size(); ++i)
      |                  ~~^~~~~~~~~~
parks.cpp:116:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |  if(points.size() != n-1) return 0;
      |     ~~~~~~~~~~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 99 ms 25832 KB Output is correct
10 Correct 10 ms 7120 KB Output is correct
11 Correct 46 ms 16312 KB Output is correct
12 Correct 17 ms 8152 KB Output is correct
13 Correct 13 ms 9160 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5144 KB Output is correct
16 Correct 99 ms 25868 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 99 ms 25832 KB Output is correct
10 Correct 10 ms 7120 KB Output is correct
11 Correct 46 ms 16312 KB Output is correct
12 Correct 17 ms 8152 KB Output is correct
13 Correct 13 ms 9160 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5144 KB Output is correct
16 Correct 99 ms 25868 KB Output is correct
17 Incorrect 2 ms 5004 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 99 ms 25832 KB Output is correct
10 Correct 10 ms 7120 KB Output is correct
11 Correct 46 ms 16312 KB Output is correct
12 Correct 17 ms 8152 KB Output is correct
13 Correct 13 ms 9160 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5144 KB Output is correct
16 Correct 99 ms 25868 KB Output is correct
17 Incorrect 2 ms 5004 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 99 ms 25832 KB Output is correct
10 Correct 10 ms 7120 KB Output is correct
11 Correct 46 ms 16312 KB Output is correct
12 Correct 17 ms 8152 KB Output is correct
13 Correct 13 ms 9160 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5144 KB Output is correct
16 Correct 99 ms 25868 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 5004 KB Output is correct
19 Correct 2 ms 5004 KB Output is correct
20 Correct 229 ms 41744 KB Output is correct
21 Correct 245 ms 41824 KB Output is correct
22 Correct 228 ms 41772 KB Output is correct
23 Correct 222 ms 35580 KB Output is correct
24 Correct 72 ms 15404 KB Output is correct
25 Correct 77 ms 22924 KB Output is correct
26 Correct 77 ms 22820 KB Output is correct
27 Correct 238 ms 46376 KB Output is correct
28 Correct 220 ms 46320 KB Output is correct
29 Correct 213 ms 36892 KB Output is correct
30 Correct 207 ms 36944 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Correct 18 ms 7656 KB Output is correct
33 Correct 33 ms 10676 KB Output is correct
34 Correct 222 ms 41724 KB Output is correct
35 Correct 8 ms 5940 KB Output is correct
36 Correct 21 ms 9716 KB Output is correct
37 Correct 53 ms 14312 KB Output is correct
38 Incorrect 69 ms 18128 KB Solution announced impossible, but it is possible.
39 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 99 ms 25832 KB Output is correct
10 Correct 10 ms 7120 KB Output is correct
11 Correct 46 ms 16312 KB Output is correct
12 Correct 17 ms 8152 KB Output is correct
13 Correct 13 ms 9160 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5144 KB Output is correct
16 Correct 99 ms 25868 KB Output is correct
17 Incorrect 182 ms 36020 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5000 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 2 ms 5004 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 99 ms 25832 KB Output is correct
10 Correct 10 ms 7120 KB Output is correct
11 Correct 46 ms 16312 KB Output is correct
12 Correct 17 ms 8152 KB Output is correct
13 Correct 13 ms 9160 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 3 ms 5144 KB Output is correct
16 Correct 99 ms 25868 KB Output is correct
17 Incorrect 2 ms 5004 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -