oj.uz

Submission #113681

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

using namespace std;
#define ll long long
struct point{
	ll x, y;
	int indx;
	
	point(){
		x = 0, y = 0; indx = -10000;
	}
	point(ll X, ll 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);
	}
};

ll 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) > 0LL;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	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;
	}
	bitset<10005> R; R.flip();
	for(int i = 0; i < n; i++){
		//cout<<"DOING POint"<<i<<endl;
		//considering point i as center
		vector<point> p; p.reserve(n+camps.size());
		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;
		bitset<10005> reach; 
		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 || reach[p[i].indx*-1-1]) 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 || reach[p[i].indx*-1-1]) break;
			reach[p[i].indx*-1 - 1] = true;
		}
		//cout<<"LOLOL"<<endl;
		R &= reach;
	}
	assert(R[0]);
	vector<int> ans;
	for(int i = 1; i <= c; 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:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < camps.size(); j++){
                  ~~^~~~~~~~~~~~~~
fangorn.cpp:68: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:72:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(indx != -1 && indx != p.size());
                        ~~~~~^~~~~~~~~~~

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 384 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 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 5 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 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 114 ms 428 KB Output is correct
5 Correct 25 ms 384 KB Output is correct
6 Correct 475 ms 504 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 532 KB Output is correct
2 Execution timed out 3062 ms 904 KB Time limit exceeded
3 Halted 0 ms 0 KB -