Submission #45566

#	Time	Username	Problem	Language	Result	Execution time	Memory
45566		qoo2p5	Port Facility (JOI17_port_facility)	C++17	22 / 100	6095 ms	384184 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

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

const int N = (int) 1e6 + 123;
const ll MOD = (ll) 1e9 + 7;

int n;
int a[N], b[N];
vector<int> g[N];
int col[N];

void dfs(int v, int cc = 1) {
    col[v] = cc;
    for (int u : g[v]) {
        if (!col[u]) {
            dfs(u, 3 - cc);
        }
        if (col[u] != 3 - cc) {
            cout << "0\n";
            exit(0);
        }
    }
}

bool closed[N];
pair<int, bool> what[2 * N];

void run() {    
    cin >> n;
    rep(i, 0, n) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        what[a[i]] = {i, 0};
        what[b[i]] = {i, 1};
    }
    
    int e = 0;
    
    vector<int> st, tmp;
    rep(i, 0, 2 * n) {
        int v = what[i].first;
        
        if (what[i].second) {
            while (1) {
                int t = st.back();
                st.pop_back();
                if (t == v) {
                    break;
                }
                if (!closed[t]) {
                    tmp.pb(t);
                }
            }
            
            for (int u : tmp) {
                g[u].pb(v);
                g[v].pb(u);
                e++;
            }
            
            while (sz(tmp)) {
                int u = tmp.back();
                tmp.pop_back();
                st.pb(u);
            }
            
            closed[v] = 1;
        } else {
            st.pb(v);
        }
    }
    
    ll ans = 1;
    
    rep(i, 0, n) {
        if (!col[i]) {
            dfs(i);
            ans = (ans * 2) % MOD;
        }
    }
    
    cout << ans << "\n";
}

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