Submission #1223262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223262		rythm_of_knight	Port Facility (JOI17_port_facility)	C++17	0 / 100	10 ms	23876 KiB

port_facility

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 6, mod = 1e9 + 7;
vector <int> g[N];
int f[N], sz[N], d[N];

int father(int x) {
    if (f[x] != f[f[x]])
        return f[x] = father(f[x]);
    return f[x];
}

void dsu(int a, int b) {
    int sa = a, sb = b;
    a = father(a), b = father(b);
    if (a == b)
        return;
    // cout << sa << ' ' << sb << '\n';
    g[sa].push_back(sb);
    g[sb].push_back(sa);
    if (sz[a] < sz[b])
        swap(a, b);
    f[b] = a;
    sz[a] += sz[b];
}

void dfs(int x, int par) {
    d[x] = d[par] + 1;
    for (int y : g[x])
        if (y != par)
            dfs(y, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int m = n << 1;
    vector <int> p(m + 1, -1), w(m + 1);
    for (int i = 1; i <= n; i++) {
        f[i] = i, sz[i] = 1;
        int a, b;
        // cout << i << ": " << flush;
        cin >> a >> b;
        p[a] = 0;
        p[b] = a;
        w[a] = w[b] = i;
    }
    vector <ar <int, 3>> pos;
    int st = -1;
    for (int cur = 1; cur <= m; cur++) {
        if (!p[cur]) {
            int tmp = pos.size();
            pos.push_back({cur, st, tmp + 1});
            st = tmp;
        } else {
            int j = st;
            while (j >= 0 && pos[j][0] > p[cur]) {
                dsu(w[pos[j][0]], w[cur]);
                j = pos[j][1];
            }
            if (j >= 0 && pos[j][0] == p[cur]) {
                if (pos[j][1] >= 0)
                    pos[pos[j][1]][2] = pos[j][2];
                if (pos[j][2] < pos.size())
                    pos[pos[j][2]][1] = pos[j][1];
                else if (st == j)
                    st = pos[j][1];
                else
                    while (true) cout << "something\n" << flush;
                j = pos[j][1];
            }
            int k = j; j = st;
            while (j > k) {
                int nxt = pos[j][1];
                pos[j][1] = k;
                pos[j][2] = pos.size();
                j = nxt;
            }
        }
    }
    int com = 0;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            dfs(i, 0);
            com++;
        }
    }
    vector <int> ps[2];
    for (int i = 1; i <= m; i++) {
        if (!p[i]) {
            ps[d[w[i]] & 1].push_back(i);
        } else {
            int b = d[w[i]] & 1;
            if (!ps[b].empty() && ps[b].back() > p[i])
                return cout << 0, 0;
            ps[b].pop_back();
        }
    }
    int ans = 1;
    for (int i = 1; i <= com; i++)
        (ans <<= 1) %= mod;
    cout << ans;
}

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