Submission #1044727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044727		earlyamazon	Port Facility (JOI17_port_facility)	C++14	22 / 100	6099 ms	81320 KiB

port_facility

// n <= 2000

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int mn = 1e6+7;
int n, kt;
vector<pair<int,int>> t;
vector<int> G[mn*2];
int odw[mn*2];
bool dwu = 1;

bool krawedz(pair<int,int> a, pair<int,int> b){
    return (a.first < b.first && b.first < a.second) ^ (a.first < b.second && b.second < a.second);
}

void dfs(int v){
    odw[v] = kt;
    if ((v < n && odw[v+n] == kt) || (v >= n && odw[v-n] == kt)) dwu = 0;
    for (auto i : G[v]){
        if (!odw[i]) dfs(i);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cout.tie(0);
    cin>>n;
    for (int i = 0; i < n; i++){
        int a,b;
        cin>>a>>b;
        t.push_back({a,b});
    }
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (krawedz(t[i], t[j])){
                G[i].push_back(j+n);
                G[j+n].push_back(i);
                G[i+n].push_back(j);
                G[j].push_back(i+n);
                // cout<<i<<" "<<j<<"\n";
            }
        }
    }
    for (int i = 0; i < n; i++){
        if (!odw[i] && !odw[i+n]){
            kt++;
            dfs(i);
        }
    }
    int w = 1;
    if (!dwu) w = 0;
    for (int i = 0; i < kt; i++) w = (w*2)%mod;
    cout<<w<<"\n";
}

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