Submission #465064

#	Time	Username	Problem	Language	Result	Execution time	Memory
465064		blue	Port Facility (JOI17_port_facility)	C++17	100 / 100	1577 ms	126048 KiB

port_facility

#include <iostream>
#include <vector>
using namespace std;

const int maxN = 1'000'000;
const int mod = 1e9 + 7;

vector<int> edge[1+maxN];
vector<int> A(1+maxN), B(1+maxN);

void add_edge(int u, int v)
{
    edge[u].push_back(v);
    edge[v].push_back(u);
    // cerr << "edge " << u << ' ' << v << '\n';
}

bool no_sol = 0;
vector<int> color(1+maxN, -1);
int comp = 0;

void dfs(int u)
{
    for(int v: edge[u])
    {
        if(color[v] == !color[u]) continue;
        else if(color[v] == color[u]) no_sol = 1;
        else
        {
            color[v] = !color[u];
            dfs(v);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<int> event(1+2*N);
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i] >> B[i];
        event[A[i]] = +i;
        event[B[i]] = -i;
    }

    // cerr << "check\n";


    vector<int> S;
    for(int e = 1; e <= 2*N; e++)
    {
        if(event[e] > 0) continue;
        // cerr << "e = " << e << '\n';

        while(!S.empty() && A[-event[e]] < A[S.back()])
        {
            // cerr << "popping " << S.back() << '\n';
            S.pop_back();
        }

        // if(!S.empty())
        //     cerr << A[-event[e]] << ' ' << B[S.back()] << '\n';

        if(!S.empty() && A[-event[e]] < B[S.back()])
            add_edge(-event[e], S.back());

        S.push_back(-event[e]);
    }

    S.clear();
    for(int e = 2*N; e >= 1; e--)
    {
        if(event[e] < 0) continue;

        while(!S.empty() && B[S.back()] < B[event[e]])
            S.pop_back();

        if(!S.empty() && A[S.back()] < B[event[e]])
            add_edge(event[e], S.back());

        S.push_back(event[e]);
    }


    for(int i = 1; i <= N; i++)
    {
        if(color[i] != -1) continue;
        comp++;

        color[i] = 0;
        dfs(i);
    }

    if(no_sol == 0)
    {
        vector<int> T[2];
        for(int e = 1; e <= 2*N; e++)
        {
            if(event[e] > 0)
            {
                T[ color[event[e]] ].push_back(event[e]);
            }
            else
            {
                if(T[ color[-event[e]] ].back() == -event[e])
                    T[ color[-event[e]] ].pop_back();
                else
                    no_sol = 1;
            }
        }
    }

    if(no_sol)
    {
        cout << "0\n";
    }
    else
    {
        int ans = 1;
        for(int x = 1; x <= comp; x++) ans = (2 * ans) % mod;
        cout << ans << '\n';
    }
}

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