Submission #772064

#	Time	Username	Problem	Language	Result	Execution time	Memory
772064		Ahmed57	Port Facility (JOI17_port_facility)	C++17	100 / 100	1249 ms	76748 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
//DSU
int pr[2000001];
int gs[2000001];

int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return pr[x] = findleader(pr[x]);
}
bool samegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    return led1==led2;
}
void mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
    }
}
signed main(){
    int n;cin>>n;
    for(int i = 0;i<=2*n;i++)pr[i] = i , gs[i] = 1;
    vector<pair<int,int>> v(n);
    for(int i = 0;i<n;i++){
        cin>>v[i].first>>v[i].second;
    }
    sort(v.begin(),v.end());
    map<int,int> s;
    for(int i = 0;i<v.size();i++){
        auto it = s.lower_bound(v[i].first) , it2 = s.lower_bound(v[i].second);
        if(it!=it2&&it2!=s.begin()){
            it2--;
            while(it!=s.end()){
                mergegroup(i+n,it->second);
                mergegroup(i,it->second+n);
                if(it==it2||samegroup(it2->second,it->second))break;
                it++;
            }
        }
        s[v[i].second] = i;
    }
    long long ans = 1 , mod = 1000000007;
    for(int i = 0;i<n;i++){
        if(samegroup(i,i+n))ans = 0;
        if(findleader(i)==i||findleader(i)==i+n)ans=(ans*2)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

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