Submission #955088

#	Time	Username	Problem	Language	Result	Execution time	Memory
955088		Abito	Port Facility (JOI17_port_facility)	C++17	22 / 100	6102 ms	61520 KiB

port_facility

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=1e6+5,M=1e9+7;
int n,l[N],r[N];
vector<int> adj[N];
bool c[N],vis[N];
int pow(int x,int y){
    if (!y) return 1;
    int z=pow(x,y/2);
    z=z*z%M;
    if (y&1) z=z*x%M;
    return z;
}
void dfs(int x,bool col){
    c[x]=col;vis[x]=1;
    for (auto u:adj[x]) if (!vis[u]) dfs(u,!col);
    return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>l[i]>>r[i];
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            int L=max(l[i],l[j]),R=min(r[i],r[j]);
            if (L>R) continue;
            if (L==l[i] && R==r[i]) continue;
            if (L==l[j] && R==r[j]) continue;
            adj[i].pb(j);
            adj[j].pb(i);
        }
    }
    int cmp=0;
    for (int i=1;i<=n;i++){
        if (vis[i]) continue;
        dfs(i,0);
        cmp++;
    }
    bool ok=true;
    for (int i=1;i<=n;i++) for (auto u:adj[i]) ok&=(c[u]!=c[i]);
    cout<<pow(2,cmp)*ok<<endl;
    return 0;
}

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