Submission #57668

#	Time	Username	Problem	Language	Result	Execution time	Memory
57668		spencercompton	Port Facility (JOI17_port_facility)	C++17	22 / 100	6024 ms	34168 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> comp[1000000];
vector<int> sz;
vector<int> id;
vector<bool> red;
class Ed{
	public:
		int id, s, e;
		Ed(int a, int b, int c){
			id = a;
			s = b;
			e = c;
		}
		bool operator<(const Ed &o) const{
			return s<o.s;
		}
};
vector<Ed> li;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll mod = 1000000007LL;
	int n;
	cin >> n;
	int st[n];
	int en[n];
	for(int i = 0; i<n; i++){
		red.push_back(true);
		id.push_back(i);
		sz.push_back(1);
		comp[i].push_back(i);
		int a, b;
		cin >> a >> b;
		st[i] = a;
		en[i] = b;
		li.push_back(Ed(i,a,b));
	}
	sort(li.begin(),li.end());
	priority_queue<Ed> pq; 
	int po = n;
	bool in[n];
	//talking about components
	bool inside[n];
	//talking about elements
	int last[n];
	for(int i = 0; i<n; i++){
		inside[i] = false;
		in[i] = false;
		last[i] = -1;
	}
	priority_queue<Ed> all[n];
	for(int i = 0; i<li.size(); i++){
		for(int j = 0; j<i; j++){
			if(li[j].e > li[i].s && li[j].e < li[i].e){
				int ca = id[li[i].id];
				int cb = id[li[j].id];
				if(ca==cb){
					continue;
				}
				po--;
				bool flip = red[li[i].id] == red[li[j].id];
				if(sz[ca]>sz[cb]){
					swap(ca,cb);
				}
				//ca into cb
				for(int k = 0; k<comp[ca].size(); k++){
					comp[cb].push_back(comp[ca][k]);
					sz[cb]++;
					if(flip){
						red[comp[ca][k]] = !red[comp[ca][k]];
					}
					id[comp[ca][k]] = cb;
				}
			}
		}
		// vector<int> conflict;
		// while(pq.size()>0 && -pq.top().s <li[i].s){
		// 	int cur = pq.top().id;
		// 	inside[cur] = false;
		// 	pq.pop();
		// 	while(all[id[cur]].size()>0 && -all[id[cur]].top().s<li[i].s){
		// 		inside[all[id[cur]].top().id] = false;
		// 		all[id[cur]].pop();
		// 	}
		// 	if(all[id[cur]].size()>0 && !inside[all[id[cur]].top().id]){
		// 		Ed ee = all[id[cur]].top();
		// 		pq.push(Ed(ee.id, ee.s,6969));
		// 		inside[ee.id] = true;
		// 	}
		// }
		// while(pq.size()>0 && -pq.top().s <li[i].e){
		// 	int cur = pq.top().id;
		// 	conflict.push_back(cur);

		// 	inside[cur] = false;
		// 	int ca = id[li[i].id];
		// 	int cb = id[cur];

			
		// 	pq.pop();
		// 	if(ca==cb){
		// 		continue;
		// 	}
		// 	po--;
		// 	bool flip = red[li[i].id] == red[cur];
		// 	if(sz[ca]>sz[cb]){
		// 		swap(ca,cb);
		// 	}
		// 	//ca into cb
		// 	for(int j = 0; j<comp[ca].size(); j++){
		// 		comp[cb].push_back(comp[ca][j]);
		// 		sz[cb]++;
		// 		if(flip){
		// 			red[comp[ca][j]] = !red[comp[ca][j]];
		// 		}
		// 		id[comp[ca][j]] = cb;
		// 	}
		// 	comp[ca].clear();
		// 	while(all[ca].size()>0){
		// 		all[ca].pop();
		// 	}
		// }
		// conflict.push_back(li[i].id);
		// inside[li[i].id] = false;
		// vector<int> use;
		// for(int j = 0; j<conflict.size(); j++){
		// 	if(!in[id[conflict[j]]]){
		// 		use.push_back(id[conflict[j]]);
		// 		in[id[conflict[j]]] = true;
		// 	}
		// 	if(last[conflict[j]] != id[conflict[j]]){
		// 		all[id[conflict[j]]].push(Ed(conflict[j],-en[conflict[j]],696969));
		// 		last[conflict[j]] = id[conflict[j]];
		// 	}
		// }
		// for(int j = 0; j<use.size(); j++){
		// 	int cur = use[j];
		// 	if(all[cur].size()>0 && !inside[all[cur].top().id]){
		// 		inside[all[cur].top().id] = true;
		// 		pq.push(all[cur].top());
		// 	}
		// 	in[cur] = false;
		// }
	}
	ll ans = 1LL;
	for(int i = 0; i<po; i++){
		ans *= 2LL;
		ans %= mod;
	}
	bool ok = true;
	priority_queue<int> reds;
	priority_queue<int> blues;
	for(int i = 0; i<n; i++){
		for(int j = i+1; j<n; j++){
			if(li[i].e > li[j].s && li[i].e < li[j].e && red[li[i].id] == red[li[j].id]){
				ok = false;
			}
		}
	}
	// for(int i = 0; i<li.size(); i++){
	// 	while(reds.size()>0 && -reds.top() < li[i].s){
	// 		reds.pop();
	// 	}
	// 	while(blues.size()>0 && -blues.top() < li[i].s){
	// 		blues.pop();
	// 	}
	// 	if(!red[li[i].id]){
	// 		if(blues.size()>0 && -blues.top()<li[i].e){
	// 			ok = false;
	// 		}
	// 		blues.push(-li[i].e);
	// 	}
	// 	else{
	// 		if(reds.size()>0 && -reds.top() < li[i].e){
	// 			ok = false;
	// 		}
	// 		reds.push(-li[i].e);
	// 	}
	// }
	if(!ok){
		ans = 0LL;
	}
	assert(ans>=0);
	cout << ans << endl;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<li.size(); i++){
                 ~^~~~~~~~~~
port_facility.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k = 0; k<comp[ca].size(); k++){
                    ~^~~~~~~~~~~~~~~~
port_facility.cpp:27:6: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  int st[n];
      ^~
port_facility.cpp:28:6: warning: variable 'en' set but not used [-Wunused-but-set-variable]
  int en[n];
      ^~
port_facility.cpp:43:7: warning: variable 'in' set but not used [-Wunused-but-set-variable]
  bool in[n];
       ^~
port_facility.cpp:45:7: warning: variable 'inside' set but not used [-Wunused-but-set-variable]
  bool inside[n];
       ^~~~~~
port_facility.cpp:47:6: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  int last[n];
      ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22