Submission #1300566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300566		purplelemon	Port Facility (JOI17_port_facility)	C++20	100 / 100	1741 ms	262196 KiB

port_facility

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

const int N = 1e6+6, MOD = 1e9+7;
int n;
pair<int,int> nums[N];
int mark[2*N], match[2*N];
bool badr[N];
set<pair<int,int>> hast, nor;
vector<pair<int,int>> G[N];
int is[N];

void DFS(int v) {
    for (auto u : G[v]) {
        if (!is[u.first]) {
            is[u.first] = (is[v]+u.second*is[v])%3;
            DFS(u.first);
        } else if (is[u.first] != ((is[v]+u.second*is[v])%3)) {
            cout << 0;
            exit(0);
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> nums[i].first >> nums[i].second;
        mark[nums[i].first] = i;
        mark[nums[i].second] = i;
        match[nums[i].first] = nums[i].second;
        match[nums[i].second] = nums[i].first;
    }
    for (int i = 1;i <= 2*n;i++) {
        if (match[i] > i) {
            hast.insert({i,mark[i]});
            nor.insert({i,mark[i]});
        } else {
            if (nor.find({match[i],mark[i]}) == nor.end()) {
                cout << 0;
                return;
            }
            vector<pair<int,int>> rem;
            
            auto fix = hast.find({match[i],mark[i]});
            fix++;
            if (fix != hast.end()) {
                G[mark[i]].push_back({fix->second,1});
                G[fix->second].push_back({mark[i],1});
                badr[mark[i]] = 1;
            }
            for (auto it = nor.upper_bound({match[i],mark[i]});it != nor.end();it++) {
                auto it2 = hast.find(*it);
                int v = it->second;
                it2++;
                if (it2 != hast.end()) {
                    if (badr[v]) {
                        cout << 0;
                        return;
                    }
                    G[v].push_back({it2->second,0});
                    G[it2->second].push_back({v,0});
                    rem.push_back(*it);
                }
            }
            for (auto val : rem) nor.erase(val);
            auto nxt = fix;
            fix--;
            if (nxt != hast.end() && fix != hast.begin()) {
                fix--;
                auto prev = fix;
                fix++;
                if (badr[prev->second]) {
                    badr[prev->second] = 0;
                    nor.erase(*prev);
                } else if (nor.find(*prev) == nor.end()) {
                    badr[prev->second] = 1;
                    nor.insert(*prev);
                }
            } else if (fix != hast.begin()) {
                fix--;
                badr[fix->second] = 0;
                nor.insert(*fix);
            }
            badr[mark[i]] = 0;
            hast.erase({match[i],mark[i]});
            nor.erase({match[i],mark[i]});
        }
        // cout << i << '\n';
        // cout << "hast : ";
        // for (auto val : hast) {
        //     cout << val.first << ' ' << val.second << " - ";
        // }
        // cout << '\n';
        // cout << "nor : ";
        // for (auto val : nor) {
        //     cout << val.first << ' ' << val.second << " - ";
        // }
        // cout << '\n';
        // cout << "badr : ";
        // for (int i = 1;i <= n;i++) {
        //     cout << i << ',' << badr[i] << "  ";
        // }
        // cout << '\n';
    }
    // for (int i = 1;i <= n;i++) {
    //     cout << i << " : ";
    //     for (auto u : G[i]) {
    //         cout << u.first << ' ' << u.second << " - ";
    //     }
    //     cout << '\n';
    // }
    int c = 0;
    for (int i = 1;i <= n;i++) {
        if (!is[i]) {
            is[i] = 1;
            DFS(i);
            c++;
        }
    }
    int ans = 1;
    for (int i = 0;i < c;i++) {
        ans = (ans*2)%MOD;
    }
    cout << ans;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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