oj.uz

Submission #440935

# Submission time Handle Problem Language Result Execution time Memory
440935 2021-07-03T13:50:57 Z ogibogi2004 Fountain Parks (IOI21_parks) C++17
5 / 100
 355 ms 30884 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct point
{
	int x,y,idx;
	bool operator<(point const& other)const
	{
		return y<other.y;
	}
};
map<pair<int,int>,int>number;
int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    vector<point>v[2];
    int n=x.size();
    for(int i=0;i<n;i++)
    {
		number[{x[i],y[i]}]=i;
		if(x[i]==2)v[0].push_back({x[i],y[i],i});
		else v[1].push_back({x[i],y[i],i});
	}
	if(v[0].size()==0)
	{
		sort(v[1].begin(),v[1].end());
		vector<int>ans1,ans2,ans3,ans4;
		for(int i=1;i<v[1].size();i++)
		{
			if(v[1][i].y-v[1][i-1].y>2)return 0;
			ans1.push_back(v[1][i-1].idx);
			ans2.push_back(v[1][i].idx);
			ans3.push_back(3);
			ans4.push_back(v[1][i].y-1);
		}
		build(ans1,ans2,ans3,ans4);
		return 1;
	}
	if(v[1].size()==0)
	{
		sort(v[0].begin(),v[0].end());
		vector<int>ans1,ans2,ans3,ans4;
		for(int i=1;i<v[0].size();i++)
		{
			if(v[0][i].y-v[0][i-1].y>2)return 0;
			ans1.push_back(v[0][i-1].idx);
			ans2.push_back(v[0][i].idx);
			ans3.push_back(3);
			ans4.push_back(v[0][i].y-1);
		}
		build(ans1,ans2,ans3,ans4);
		return 1;
	}
	sort(v[0].begin(),v[0].end());
	sort(v[1].begin(),v[1].end());
	vector<pair<int,int> >intervals[2];
	int l=v[0][0].y;
	vector<int>ans1,ans2,ans3,ans4;
	for(int i=1;i<v[0].size();i++)
	{
		if(v[0][i].y-v[0][i-1].y!=2)
		{
			intervals[0].push_back({l,v[0][i-1].y});
			l=v[0][i].y;
		}
		else
		{
			ans1.push_back(v[0][i-1].idx);
			ans2.push_back(v[0][i].idx);
			ans3.push_back(v[0][i-1].x-1);
			ans4.push_back(v[0][i-1].y+1);
		}
	}
	intervals[0].push_back({l,v[0].back().y});
	l=v[1][0].y;
	for(int i=1;i<v[1].size();i++)
	{
		if(v[1][i].y-v[1][i-1].y!=2)
		{
			intervals[1].push_back({l,v[1][i-1].y});
			l=v[1][i].y;
		}
		else
		{
			ans1.push_back(v[1][i-1].idx);
			ans2.push_back(v[1][i].idx);
			ans3.push_back(v[1][i-1].x+1);
			ans4.push_back(v[1][i-1].y+1);
		}
	}
	intervals[1].push_back({l,v[1].back().y});
	for(int i1=0;i1<intervals[0].size();i1++)
	{
		for(int i2=0;i2<intervals[1].size();i2++)
		{
			if(intervals[0][i1].second<intervals[1][i2].first)continue;
			if(intervals[0][i1].first>intervals[1][i2].second)continue;
			int p1=min(intervals[0][i1].second,intervals[1][i2].second);
			ans1.push_back(number[{2,p1}]);
			ans2.push_back(number[{4,p1}]);
			ans3.push_back(3);
			ans4.push_back(p1-1);
		}
	}
	build(ans1,ans2,ans3,ans4);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=1;i<v[1].size();i++)
      |               ~^~~~~~~~~~~~
parks.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=1;i<v[0].size();i++)
      |               ~^~~~~~~~~~~~
parks.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=1;i<v[0].size();i++)
      |              ~^~~~~~~~~~~~
parks.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=1;i<v[1].size();i++)
      |              ~^~~~~~~~~~~~
parks.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i1=0;i1<intervals[0].size();i1++)
      |               ~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int i2=0;i2<intervals[1].size();i2++)
      |                ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 131 ms 14520 KB Output is correct
10 Correct 9 ms 1748 KB Output is correct
11 Correct 48 ms 7756 KB Output is correct
12 Correct 14 ms 2440 KB Output is correct
13 Correct 35 ms 4924 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 150 ms 14416 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 131 ms 14520 KB Output is correct
10 Correct 9 ms 1748 KB Output is correct
11 Correct 48 ms 7756 KB Output is correct
12 Correct 14 ms 2440 KB Output is correct
13 Correct 35 ms 4924 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 150 ms 14416 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Given structure is not connected: There is no path between vertices 0 and 1
22 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 131 ms 14520 KB Output is correct
10 Correct 9 ms 1748 KB Output is correct
11 Correct 48 ms 7756 KB Output is correct
12 Correct 14 ms 2440 KB Output is correct
13 Correct 35 ms 4924 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 150 ms 14416 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Given structure is not connected: There is no path between vertices 0 and 1
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 131 ms 14520 KB Output is correct
10 Correct 9 ms 1748 KB Output is correct
11 Correct 48 ms 7756 KB Output is correct
12 Correct 14 ms 2440 KB Output is correct
13 Correct 35 ms 4924 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 150 ms 14416 KB Output is correct
17 Incorrect 1 ms 204 KB Tree (a[0], b[0]) = (3, 1) is not adjacent to edge between u[0]=0 @(200000, 2) and v[0]=2 @(199998, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 131 ms 14520 KB Output is correct
10 Correct 9 ms 1748 KB Output is correct
11 Correct 48 ms 7756 KB Output is correct
12 Correct 14 ms 2440 KB Output is correct
13 Correct 35 ms 4924 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 150 ms 14416 KB Output is correct
17 Incorrect 355 ms 30884 KB Pair u[50000]=39414 @(87196, 2) and v[50000]=87394 @(100002, 4) does not form a valid edge (distance != 2)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 131 ms 14520 KB Output is correct
10 Correct 9 ms 1748 KB Output is correct
11 Correct 48 ms 7756 KB Output is correct
12 Correct 14 ms 2440 KB Output is correct
13 Correct 35 ms 4924 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 3 ms 460 KB Output is correct
16 Correct 150 ms 14416 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 0 ms 204 KB Given structure is not connected: There is no path between vertices 0 and 1
22 Halted 0 ms 0 KB -