Submission #471449

#	Time	Username	Problem	Language	Result	Execution time	Memory
471449		Rainbowbunny	Port Facility (JOI17_port_facility)	C++17	100 / 100	1038 ms	83396 KiB

port_facility

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

const int MAXN = 1000005;
const int mod = 1e9 + 7;

int n, ans = 1;
int dsu[2 * MAXN];
pair <int, int> A[MAXN];
map <int, int> M;

int Root(int node)
{
    return dsu[node] == node ? node : dsu[node] = Root(dsu[node]);
}

void Union(int x, int y)
{
    x = Root(x);
    y = Root(y);
    if(x == y)
    {
        return;
    }
    dsu[x] = y;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> A[i].first >> A[i].second;
        dsu[i] = i;
        dsu[i + n] = i + n;
    }
    sort(A + 1, A + n + 1);
    for(int i = 1; i <= n; i++)
    {
        map <int, int> :: iterator it1 = M.lower_bound(A[i].first);
        map <int, int> :: iterator it2 = M.lower_bound(A[i].second);
        while(it1 != it2)
        {
            Union(i, it1->second + n);
            Union(i + n, it1->second);
            if(Root(i) == Root(i + n))
            {
                cout << 0 << '\n';
                return 0;
            }
            if(Root(it1->second) == Root(it1->second + n))
            {
                cout << 0 << '\n';
                return 0;
            }
            int id = prev(it2)->second;
            if(Root(id) == Root(it1->second))
            {
                break;
            }
            it1++;
        }
        M[A[i].second] = i;
    }
    for(int i = 1; i <= n; i++)
    {
        if(Root(i) == i)
        {
            ans = ans * 2 % mod;
        }
    }
    cout << ans << '\n';
}

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