Submission #594894

#	Time	Username	Problem	Language	Result	Execution time	Memory
594894		Cross_Ratio	Port Facility (JOI17_port_facility)	C++14	22 / 100	6038 ms	32828 KiB

port_facility

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int p = 1e9 + 7;
struct UnionFind {
    vector<int> root;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x);
        y = Find(y);
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
int power(int a, int b, int c) {
    if(b==0) return 1;
    if(b==1) return a;
    if(b%2==0) {
        int k = power(a, b/2, c);
        return k * k % c;
    }
    else {
        return power(a, b-1, c) * a % c;
    }
}
int A[1000005];
int B[1000005];
vector<vector<int>> adj;
int dis[1000005];
bool isPos = true;
void dfs(int c, int pt) {
    dis[c] = pt;
    for(int n : adj[c]) {
        if(dis[n]==-1) dfs(n, pt+1);
        else {
            if(abs(dis[n]-dis[c])%2==0) isPos = false;
        }
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    adj.resize(N);
    for(i=0;i<N;i++) cin >> A[i] >> B[i];
    for(i=0;i<N;i++) dis[i] = -1;
    for(i=0;i<N;i++) {
        for(j=i+1;j<N;j++) {
            if(A[i]<A[j]&&B[i]<B[j]&&A[j]<B[i]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
            if(A[i]>A[j]&&B[i]>B[j]&&B[j]>A[i]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    int cnt = 0;
    for(i=0;i<N;i++) {
        if(dis[i]==-1) {
            dfs(i, 0);
            cnt++;
        }
    }
    cout << (isPos ? power(2, cnt, p) : 0);
}

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