oj.uz

Submission #436771

# Submission time Handle Problem Language Result Execution time Memory
436771 2021-06-24T21:00:27 Z Apiram Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 26028 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
struct point {
	int x,y,index;
};
bool dist(point x,point y){
	if (((x.x - y.x)*(x.x - y.x)+(x.y-y.y)*(x.y - y.y))!=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;
		}
	}
	return -1;
}
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) ;
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{
    	vector<vector<int>>adj(n);
    	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;
    });
    	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);
    		adj[i].push_back(i-1);
    		adj[i-1].push_back(i);
    		p[ansx.back()/2][ansy.back()/2]=true;
    		}
    		}
    		int j = i;
    
    	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);
    		adj[i].push_back(i-1);
    		adj[i-1].push_back(i);
    		p[ansx.back()/2][ansy.back()/2]=true;
    		}
    	}

    	for (int  k =0;k<j;++k){
    		int left = j,right = n-1;
    		while(left<=right){
    			int mid = (left + right)>>1;
    			if (arr[mid].y==arr[k].y){
    			int first1 =  min(arr[k].x,arr[mid].x) + 1;
   				int second1 = 	min(arr[k].y,arr[mid].y) + 1;
   				int second2=min(arr[k].y,arr[mid].y) - 1;
   				if (!p[first1/2][second2/2]){
   					ansx.push_back(first1);
    				ansy.push_back(second2);
    				ansxi.push_back(arr[k].index);
    				ansyi.push_back(arr[mid].index);
    				adj[mid].push_back(k);
    				adj[k].push_back(mid);
    				p[ansx.back()/2][ansy.back()/2]=true;
   				}		
   				else if (!p[first1/2][second1/2]){
   					ansx.push_back(first1);
    				ansy.push_back(second1);
    				ansxi.push_back(arr[k].index);
    				ansyi.push_back(arr[mid].index);
    				adj[mid].push_back(k);
    				adj[k].push_back(mid);
    				p[ansx.back()/2][ansy.back()/2]=true;
    			}
    			break;
    			}
    			else if (arr[mid].y<arr[k].y){
    				left=mid+1;
    			}
    			else right = mid-1;
    		}
    	}
		vector<bool>visited(n,false);
		queue<int>q;
		
		q.push(0);
		while(!q.empty()){
			int u =q.front();
			q.pop();
			visited[u]=true;
			for (auto x:adj[u]){
				if (!visited[x]){
				q.push(x);
				visited[u]=true;}
			}
		}
		for (auto x:visited){
			if (!x)return 0;
		}
		build(ansxi,ansyi,ansx,ansy);
    return 1;
}}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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 1 ms 204 KB Output is correct
6 Correct 1 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 70 ms 8116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 42 ms 4424 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 12 ms 2164 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 72 ms 8192 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 1 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 1 ms 204 KB Output is correct
6 Correct 1 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 70 ms 8116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 42 ms 4424 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 12 ms 2164 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 72 ms 8192 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Execution timed out 3526 ms 24372 KB Time limit exceeded
24 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 1 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 1 ms 204 KB Output is correct
6 Correct 1 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 70 ms 8116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 42 ms 4424 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 12 ms 2164 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 72 ms 8192 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Execution timed out 3526 ms 24372 KB Time limit exceeded
24 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 1 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 1 ms 204 KB Output is correct
6 Correct 1 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 70 ms 8116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 42 ms 4424 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 12 ms 2164 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 72 ms 8192 KB Output is correct
17 Runtime error 1 ms 460 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 1 ms 204 KB Output is correct
2 Correct 1 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 1 ms 204 KB Output is correct
6 Correct 1 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 70 ms 8116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 42 ms 4424 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 12 ms 2164 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 72 ms 8192 KB Output is correct
17 Runtime error 96 ms 26028 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 1 ms 204 KB Output is correct
2 Correct 1 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 1 ms 204 KB Output is correct
6 Correct 1 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 70 ms 8116 KB Output is correct
10 Correct 6 ms 1176 KB Output is correct
11 Correct 42 ms 4424 KB Output is correct
12 Correct 9 ms 1504 KB Output is correct
13 Correct 12 ms 2164 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 72 ms 8192 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Execution timed out 3526 ms 24372 KB Time limit exceeded
24 Halted 0 ms 0 KB -