oj.uz

Submission #113676

# Submission time Handle Problem Language Result Execution time Memory
113676 2019-05-27T17:54:36 Z Adhyyan1252 The Forest of Fangorn (CEOI14_fangorn) C++11
80 / 100
 3000 ms 1676 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

struct point{
	int x, y; 
	int indx;
	
	point(){
		x = 0, y = 0; indx = -10000;
	}
	point(int X, int Y, int Indx){
		x = X; y = Y; indx = Indx;
	}
	
	point operator-(const point& other){
		return point(x-other.x, y-other.y, indx);
	}
	point operator*(const int o){
		return point(x*o, y*o, indx);
	}
};

int cross(const point& a, const point& b){
	return (a.x*b.y - a.y*b.x);
}

bool comp(point a, point b){
	if(a.y >= 0 && b.y < 0) return true;
	if(b.y >= 0 && a.y < 0) return false;
	return cross(a, b) > 0;
}

signed main(){
	int w, h; cin>>w>>h;
	vector<point> camps(1);
	cin>>camps[0].x>>camps[0].y; camps[0].indx = 0;
	int c; cin>>c;
	camps.resize(c+1);
	for(int i = 1; i <= c; i++){
		cin>>camps[i].x>>camps[i].y; camps[i].indx = i;
	}
	int n; cin>>n;
	vector<point> points(n);
	for(int i = 0; i < n; i++){
		cin>>points[i].x>>points[i].y; points[i].indx = i;
	}
	vector<bool> R(c+1, true);
	for(int i = 0; i < n; i++){
		//cout<<"DOING POint"<<i<<endl;
		//considering point i as center
		vector<point> p;
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			p.push_back((points[i]-points[j]));
			p.back().indx = j;	
		}
		for(int j = 0; j < camps.size(); j++){
			p.push_back(camps[j]-points[i]);
			p.back().indx = p.back().indx*-1 - 1;
		}
		sort(p.begin(), p.end(), comp);
//		for(int i = 0; i < p.size(); i++) cout<<"("<<p[i].indx<<", "<<p[i].x<<", "<<p[i].y<<" )";
//		cout<<endl;
		vector<bool> reach(c+1, false);
		int indx = -1;
		for(indx = 0; indx < p.size(); indx++){
			if(p[indx].indx == -1) break;
		}
		reach[0] = true;
		assert(indx != -1 && indx != p.size());
		for(int i = (indx-1+p.size())%p.size(); i != indx; i = (i - 1 + p.size())%p.size()){
			if(p[i].indx >= 0) break;
			reach[p[i].indx*-1 - 1] = true;
		}
		for(int i = (indx+1)%p.size(); i != indx; i = (i + 1)%p.size()){
			if(p[i].indx >= 0) break;
			reach[p[i].indx*-1 - 1] = true;
		}
		//cout<<"LOLOL"<<endl;
		for(int i = 0; i < R.size(); i++){
			//cout<<"P: "<<i<<" "<<reach[i]<<endl;
			R[i] = R[i]&reach[i];
		}
	}
	assert(R[0]);
	vector<int> ans;
	for(int i = 1; i < R.size(); i++) if(R[i]) ans.push_back(i);
	cout<<ans.size()<<endl;
	for(int a: ans){
		cout<<a<<" ";
	}
	cout<<endl;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < camps.size(); j++){
                  ~~^~~~~~~~~~~~~~
fangorn.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(indx = 0; indx < p.size(); indx++){
                 ~~~~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from fangorn.cpp:1:
fangorn.cpp:73:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(indx != -1 && indx != p.size());
                        ~~~~~^~~~~~~~~~~
fangorn.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < R.size(); i++){
                  ~~^~~~~~~~~~
fangorn.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < R.size(); i++) if(R[i]) ans.push_back(i);
                 ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 120 ms 384 KB Output is correct
5 Correct 27 ms 384 KB Output is correct
6 Correct 495 ms 632 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 872 KB Output is correct
2 Execution timed out 3056 ms 1676 KB Time limit exceeded
3 Halted 0 ms 0 KB -