제출 #427001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427001		lyc	Port Facility (JOI17_port_facility)	C++14	22 / 100	6014 ms	45252 KiB

port_facility

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

const int MN = 1e6+5;
const int mod = 1e9+7;

int N;
ii C[MN];
ll ans;

vector<int> al[MN];
int col[MN];

void dfs(int u, int c) {
    if (!ans) return;

    col[u] = c;
    for (int& v : al[u]) {
        if (col[v] == -1) dfs(v,!c);
        else if (col[v] != !c) ans = 0;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N;
    FOR(i,1,N){
        int a, b; cin >> a >> b;
        C[i] = ii(a,b);
    }

    FOR(i,1,N) FOR(j,1,N) if (i != j) {
        if (C[i].first < C[j].first && C[i].second > C[j].first && C[i].second < C[j].second) {
            al[i].push_back(j);
            al[j].push_back(i);
        }
    }

    ans = 1;
    memset(col,-1,sizeof col);
    FOR(i,1,N) if (col[i] == -1) {
        //TRACE(i);
        dfs(i,0);
        if (!ans) break;
        ans = 2*ans % mod;
    }

    cout << ans << '\n';
}

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