Submission #550668

#	Time	Username	Problem	Language	Result	Execution time	Memory
550668		brunnorezendes	Port Facility (JOI17_port_facility)	C++14	22 / 100	6062 ms	208224 KiB

port_facility

#include <bits/stdc++.h>
#define f first
#define s second
#define maxn 1000001
#define mod 1000000007
 
using namespace std;
 
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef set<ii> sii;
typedef vector<int> vi;
typedef long long int ll;
 
int dsu[maxn], flag=0, opo[maxn], vis[maxn];

vi seg[8*maxn];
vii truck;
 
int find(int x){
	if(x == -1) return -1;
	if(dsu[x]==x) return x;
	else{
		dsu[x] = find(dsu[x]);
		return dsu[x];
	}
}
 
void merge(int a, int b){
	a = find(a);
	b = find(b);
	opo[b] = find(opo[b]);
	opo[a] = find(opo[a]);
	if(a == b) flag=1;
	else{
		if(opo[a]==-1 && opo[b]==-1){
			opo[a] = b;
			opo[b] = a;
		}
		else if(opo[a]==-1){
			dsu[a] = opo[b];
		}
		else if(opo[b]==-1){
			dsu[b] = opo[a];
		}
		else{
			dsu[b] = opo[a];
			dsu[opo[b]] = a;
		}
	}
}

void update(int id, int l, int r, int val, int x){
	int mid = (l+r)/2;
	seg[id].push_back(x);
	if(l<r){
		if(val<=mid) update(2*id, l, mid, val, x);
		else update((2*id)+1, mid+1, r, val, x);
	}
}

void query(int id, int l, int r, int ql, int qr, int u){
	int mid = (l+r)/2;
	if(l>=ql && r<=qr){
		for(int i=0;i<seg[id].size();i++){
			if(flag) break;
			merge(u, seg[id][i]);
		}
	}
	else if((ql>=l && ql<=r) || (qr<=r && qr>=l)){
		query(2*id, l, mid, ql, qr, u);
		query((2*id)+1, mid+1, r, ql, qr, u);
	}
}
 
int main(){
	int n, i, a, b, u, tam=1;
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a >> b;
		a--;b--;
		truck.push_back({a, b});
		dsu[i]=i;
		opo[i]=-1;
	}
	sort(truck.begin(), truck.end());
	for(i=0;i<n;i++){
		query(1, 0, (2*n)-1, truck[i].f, truck[i].s, i);
		if(flag) break;
		update(1, 0, (2*n)-1, truck[i].s, i);
	}
	if(flag) cout << "0";
	else{
		for(i=0;i<n;i++){
			a = find(i);
			if(!vis[a] && (opo[a]==-1 || !vis[opo[a]])) tam+=tam;
			if(tam>=mod) tam-=mod;
			vis[a]=1;
		}
		cout << tam;
	}
	return (0);
}

Compilation message (stderr)

port_facility.cpp: In function 'void query(int, int, int, int, int, int)':
port_facility.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i=0;i<seg[id].size();i++){
      |               ~^~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:77:18: warning: unused variable 'u' [-Wunused-variable]
   77 |  int n, i, a, b, u, tam=1;
      |                  ^

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