Submission #535660

#	Time	Username	Problem	Language	Result	Execution time	Memory
535660		Antekb	Port Facility (JOI17_port_facility)	C++14	22 / 100	6046 ms	65640 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef pair<int, int> pii;
const int N=1<<21;
pii seg[N];
vector<int> E[N];
int vis[N];
void dfs(int v, int c){
	vis[v]=c;
	for(int u:E[v]){
		if(!vis[u]){
			dfs(u, 3-c);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>seg[i].st>>seg[i].nd;
		//insert(i);
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			if(seg[i].st<seg[j].st ^ seg[i].st<seg[j].nd ^ seg[i].nd<seg[j].st ^ seg[i].nd<seg[j].nd){
				E[i].push_back(j);
				E[j].push_back(i);
			}
		}
	}
	int ile=0, ans=1;
	int mod=1e9+7;
	for(int i=0; i<n; i++){
		if(!vis[i]){
			ile++;
			ans*=2;
			if(ans>=mod)ans-=mod;
			dfs(i, 1);
		}
	}
	for(int i=0; i<n; i++){
		for(int j:E[i]){
			if(vis[i]==vis[j])ans=0;
		}
	}
	cout<<ans;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:28:16: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   28 |    if(seg[i].st<seg[j].st ^ seg[i].st<seg[j].nd ^ seg[i].nd<seg[j].st ^ seg[i].nd<seg[j].nd){
      |                ^
port_facility.cpp:28:60: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   28 |    if(seg[i].st<seg[j].st ^ seg[i].st<seg[j].nd ^ seg[i].nd<seg[j].st ^ seg[i].nd<seg[j].nd){
      |                                                            ^
port_facility.cpp:28:82: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   28 |    if(seg[i].st<seg[j].st ^ seg[i].st<seg[j].nd ^ seg[i].nd<seg[j].st ^ seg[i].nd<seg[j].nd){
      |                                                                                  ^

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