oj.uz

Submission #436708

# Submission time Handle Problem Language Result Execution time Memory
436708 2021-06-24T19:22:25 Z Apiram Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 18900 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>parent(2e5);
vector<int>siz(2e5);
void makesets(int v){
	parent[v]=v;
	siz[v]=1;
}
int findsets (int v){
	if (v==parent[v])return v;
	parent[v]=findsets(parent[v]);
	return parent[v];
}
void unionset(int a,int b){
	a = findsets(a);
	b =findsets(b);
	if (a==b)return;
	if (siz[a]<siz[b])swap(a,b);
	siz[a]+=siz[b];
	parent[b]=a;
}
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
struct point {
	int x,y,index;
};
bool dist(point x,point y){
	if (pow(x.x - y.x,2)+pow(x.y-y.y,2)!=4)return false;
	return true;
}
int binarysearch(int seg,int eq,int n,vector<point>arr){
	int left = 0;
	int right = n-1;
	while(left<=right){
		int mid = (left + right) >> 1;
		if (arr[mid].x<seg)left= mid + 1;
		else if (arr[mid].x>seg)right = mid-1;
		else {
			if (arr[mid].y<eq){
				left=mid+1;
			}
			else if (arr[mid].y>eq){
				right = mid-1;
			}
			else return mid;
		}
	}
	if (left>=0&&left<n)return left;
	return 0;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    vector<point>arr;
    int n = x.size();
    bool ok=true;
    
    for (int i = 0 ;i<n;++i){
    	if (x[i]!=x[0])ok=false;
    	arr.push_back({x[i],y[i],i});
    }
    vector<int>ansx,ansy,ansxi,ansyi;
    if (ok){
    sort(arr.begin(),arr.end(),[&](point a,point b){
    	return a.y<b.y;
    });
    
    for (int i = 1;i<n;++i){
    	if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y)+1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    	}
    	else return 0;
    }
    build(ansxi,ansyi,ansx,ansy);
    return 1;}
    else{
    	for (int i =0;i<n;++i){
    		makesets(i);
    	}
    	vector<vector<bool>>p(3,vector<bool>(1e5 + 5,false));
    	sort(arr.begin(),arr.end(),[&](point a,point b){
    		if (a.x==b.x)return a.y<b.y;
    		return a.x<b.x;
    });
    vector<int>check;
    	int i =1;
    	for (;i<n;++i){
    		if (arr[i].x!=2)break;
    		if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) - 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    		unionset(i-1,i);
    		p[ansx.back()/2][ansy.back()/2]=true;
    		}
    		else {
    			check.push_back(i);
    			check.push_back(i-1);
    		}
    	}
    		check.push_back(i);
    		check.push_back(i-1);
    
    	for (;i<n;++i){
    		if (arr[i-1].x==2)continue;
    		if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    		unionset(i-1,i);
    		p[ansx.back()/2][ansy.back()/2]=true;
    		}
    		else {
    		
    			check.push_back(i-1);
    		}
    	}
    
    	
    for (int l = 0;l<check.size();++l){
    	int k = check[l];
    	for (auto j:{binarysearch(arr[k].x+2,arr[k].y,n,arr),binarysearch(arr[k].x-2,arr[k].y,n,arr)}){
    		if (dist(arr[j],arr[k])&&findsets(j)!=findsets(k)){
    			int first1=min(arr[k].x,arr[j].x) + 1;
    		int first2=min(arr[k].x,arr[j].x) + 1;
    		int second1=min(arr[k].y,arr[j].y) + 1;
    		int second2 = min(arr[k].y,arr[j].y) - 1;
    		if (!p[first1/2][second1/2]){
    			ok=true;
    			ansx.push_back(first1);
    			ansy.push_back(second1);
    			ansxi.push_back(arr[j].index);
    			ansyi.push_back(arr[k].index);
    			unionset(j,k);
    			p[ansx.back()/2][ansy.back()/2]=true;
    			break;
    		}
    		if (!p[first1/2][second1/2]){
    			ok=true;
    			ansx.push_back(first1);
    			ansy.push_back(second2);
    			ansxi.push_back(arr[j].index);
    			ansyi.push_back(arr[k].index);
    			unionset(j,k);
    			p[ansx.back()/2][ansy.back()/2]=true;
    			break;
    		}
    		
    		}
    	}
    	
    }
    if (siz[findsets(0)]!=n)return 0;
    	  build(ansxi,ansyi,ansx,ansy);
    	  return 1;
    }
    
    
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int l = 0;l<check.size();++l){
      |                    ~^~~~~~~~~~~~~
parks.cpp:128:11: warning: unused variable 'first2' [-Wunused-variable]
  128 |       int first2=min(arr[k].x,arr[j].x) + 1;
      |           ^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 9 ms 2712 KB Output is correct
11 Correct 46 ms 5960 KB Output is correct
12 Correct 11 ms 3040 KB Output is correct
13 Correct 13 ms 3848 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 72 ms 9688 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 9 ms 2712 KB Output is correct
11 Correct 46 ms 5960 KB Output is correct
12 Correct 11 ms 3040 KB Output is correct
13 Correct 13 ms 3848 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 72 ms 9688 KB Output is correct
17 Correct 1 ms 1868 KB Output is correct
18 Correct 2 ms 1868 KB Output is correct
19 Correct 1 ms 1868 KB Output is correct
20 Correct 1 ms 1868 KB Output is correct
21 Correct 2 ms 1868 KB Output is correct
22 Correct 2 ms 1868 KB Output is correct
23 Correct 159 ms 17844 KB Output is correct
24 Correct 1 ms 1868 KB Output is correct
25 Correct 2 ms 1996 KB Output is correct
26 Correct 2 ms 2080 KB Output is correct
27 Correct 3 ms 2124 KB Output is correct
28 Correct 58 ms 8468 KB Output is correct
29 Correct 115 ms 11140 KB Output is correct
30 Correct 121 ms 15208 KB Output is correct
31 Correct 151 ms 17884 KB Output is correct
32 Correct 2 ms 1868 KB Output is correct
33 Correct 2 ms 1868 KB Output is correct
34 Correct 2 ms 1868 KB Output is correct
35 Correct 2 ms 1868 KB Output is correct
36 Correct 1 ms 1868 KB Output is correct
37 Correct 2 ms 1868 KB Output is correct
38 Correct 2 ms 1852 KB Output is correct
39 Correct 1 ms 1868 KB Output is correct
40 Correct 2 ms 1868 KB Output is correct
41 Correct 2 ms 1868 KB Output is correct
42 Correct 2 ms 1868 KB Output is correct
43 Correct 4 ms 1996 KB Output is correct
44 Correct 7 ms 2124 KB Output is correct
45 Execution timed out 3577 ms 8392 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 9 ms 2712 KB Output is correct
11 Correct 46 ms 5960 KB Output is correct
12 Correct 11 ms 3040 KB Output is correct
13 Correct 13 ms 3848 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 72 ms 9688 KB Output is correct
17 Correct 1 ms 1868 KB Output is correct
18 Correct 2 ms 1868 KB Output is correct
19 Correct 1 ms 1868 KB Output is correct
20 Correct 1 ms 1868 KB Output is correct
21 Correct 2 ms 1868 KB Output is correct
22 Correct 2 ms 1868 KB Output is correct
23 Correct 159 ms 17844 KB Output is correct
24 Correct 1 ms 1868 KB Output is correct
25 Correct 2 ms 1996 KB Output is correct
26 Correct 2 ms 2080 KB Output is correct
27 Correct 3 ms 2124 KB Output is correct
28 Correct 58 ms 8468 KB Output is correct
29 Correct 115 ms 11140 KB Output is correct
30 Correct 121 ms 15208 KB Output is correct
31 Correct 151 ms 17884 KB Output is correct
32 Correct 2 ms 1868 KB Output is correct
33 Correct 2 ms 1868 KB Output is correct
34 Correct 2 ms 1868 KB Output is correct
35 Correct 2 ms 1868 KB Output is correct
36 Correct 1 ms 1868 KB Output is correct
37 Correct 2 ms 1868 KB Output is correct
38 Correct 2 ms 1852 KB Output is correct
39 Correct 1 ms 1868 KB Output is correct
40 Correct 2 ms 1868 KB Output is correct
41 Correct 2 ms 1868 KB Output is correct
42 Correct 2 ms 1868 KB Output is correct
43 Correct 4 ms 1996 KB Output is correct
44 Correct 7 ms 2124 KB Output is correct
45 Execution timed out 3577 ms 8392 KB Time limit exceeded
46 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 9 ms 2712 KB Output is correct
11 Correct 46 ms 5960 KB Output is correct
12 Correct 11 ms 3040 KB Output is correct
13 Correct 13 ms 3848 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 72 ms 9688 KB Output is correct
17 Runtime error 3 ms 3660 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 9 ms 2712 KB Output is correct
11 Correct 46 ms 5960 KB Output is correct
12 Correct 11 ms 3040 KB Output is correct
13 Correct 13 ms 3848 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 72 ms 9688 KB Output is correct
17 Runtime error 96 ms 18900 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1868 KB Output is correct
9 Correct 72 ms 9644 KB Output is correct
10 Correct 9 ms 2712 KB Output is correct
11 Correct 46 ms 5960 KB Output is correct
12 Correct 11 ms 3040 KB Output is correct
13 Correct 13 ms 3848 KB Output is correct
14 Correct 2 ms 1868 KB Output is correct
15 Correct 3 ms 1868 KB Output is correct
16 Correct 72 ms 9688 KB Output is correct
17 Correct 1 ms 1868 KB Output is correct
18 Correct 2 ms 1868 KB Output is correct
19 Correct 1 ms 1868 KB Output is correct
20 Correct 1 ms 1868 KB Output is correct
21 Correct 2 ms 1868 KB Output is correct
22 Correct 2 ms 1868 KB Output is correct
23 Correct 159 ms 17844 KB Output is correct
24 Correct 1 ms 1868 KB Output is correct
25 Correct 2 ms 1996 KB Output is correct
26 Correct 2 ms 2080 KB Output is correct
27 Correct 3 ms 2124 KB Output is correct
28 Correct 58 ms 8468 KB Output is correct
29 Correct 115 ms 11140 KB Output is correct
30 Correct 121 ms 15208 KB Output is correct
31 Correct 151 ms 17884 KB Output is correct
32 Correct 2 ms 1868 KB Output is correct
33 Correct 2 ms 1868 KB Output is correct
34 Correct 2 ms 1868 KB Output is correct
35 Correct 2 ms 1868 KB Output is correct
36 Correct 1 ms 1868 KB Output is correct
37 Correct 2 ms 1868 KB Output is correct
38 Correct 2 ms 1852 KB Output is correct
39 Correct 1 ms 1868 KB Output is correct
40 Correct 2 ms 1868 KB Output is correct
41 Correct 2 ms 1868 KB Output is correct
42 Correct 2 ms 1868 KB Output is correct
43 Correct 4 ms 1996 KB Output is correct
44 Correct 7 ms 2124 KB Output is correct
45 Execution timed out 3577 ms 8392 KB Time limit exceeded
46 Halted 0 ms 0 KB -