Submission #44995

#	Time	Username	Problem	Language	Result	Execution time	Memory
44995		PowerOfNinjaGo	Port Facility (JOI17_port_facility)	C++17	0 / 100	168 ms	188504 KiB

port_facility

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 1e6+5;
int n;
int st[23][2*maxn];
int lend[8*maxn];
int Rend[8*maxn];
int toy[2*maxn];
int tox[2*maxn];
int p[2*maxn];
vector<int> vals;
int cc;
vector<int> comps[2*maxn];
vector<int> adj[2*maxn];
queue< ii > q;
int col[2*maxn];
const int md = 1e9+7;
void init(int p = 1, int L = 1, int R = 2*n)
{
    lend[p] = L, Rend[p] = L-1;
    if(L == R) return;
    init(2*p, L, (L+R)/2); init(2*p+1, (L+R)/2+1, R);
}
void add(int x, int val, int p = 1, int dep = 1, int L = 1, int R = 2*n)
{
    Rend[p]++;
    st[dep][Rend[p]] = val;
    if(L == R) return;
    int M = (L+R)/2;
    if(x<= M) add(x, val, 2*p, 1+dep, L, M);
    else add(x, val, 2*p+1, 1+dep, M+1, R);
}
void get(int i, int j, int key, int p = 1, int dep = 1, int L = 1, int R = 2*n)
{
    if(i> R || j< L) return;
    if(i<= L && R<= j)
    {
        while(lend[p]<= Rend[p] && st[dep][lend[p]]< key)
        {
            vals.pb(st[dep][lend[p]]);
            lend[p]++;
        }
        return;
    }
    int M = (L+R)/2;
    get(i, j, key, 2*p, dep+1, L, M); get(i, j, key, 2*p+1, dep+1, M+1, R);
}
int findset(int x)
{
    if(x == p[x]) return x;
    return p[x] = findset(p[x]);
}
void unionset(int x, int y)
{
    int a = findset(x), b = findset(y);
    if(a == b) return;
    cc--;
    p[a] = b;
}
int main()
{
    scanf("%d", &n);
    init(); cc = n;
    for(int i = 1; i<= 2*n; i++) p[i] = i;
    for(int i = 1; i<= n; i++)
    {
        int x, y; scanf("%d %d", &x, &y);
        toy[x] = y; tox[y] = x;
    }
    for(int i = 1; i<= 2*n; i++)
    {
        if(!toy[i]) continue;
        get(i, toy[i], i);
        while(!vals.empty())
        {
            int x = vals.back(); vals.pop_back();
            //printf("union %d to %d\n", x, i);
            unionset(x, i);
            adj[x].pb(i); adj[i].pb(x);
        }
        add(toy[i], i);
    }
    init();
    for(int i = 2*n; i; i--)
    {
        if(!tox[i]) continue;
        get(tox[i], i, -i);
        while(!vals.empty())
        {
            int x = -vals.back(); vals.pop_back();
            //printf("union %d to %d\n", tox[x], tox[i]);
            unionset(tox[x], tox[i]);
            adj[tox[x]].pb(tox[i]); adj[tox[i]].pb(tox[x]);
        }
        add(tox[i], -i);
    }
    int ans = 1;
    for(int i = 1; i<= 2*maxn; i++)
    {
        if(!toy[i]) continue;
        if(col[i]) continue;
        ans = (2LL*ans)%md;
        q.push(ii(i, 1));
        while(!q.empty())
        {
            ii z = q.front(); q.pop();
            //printf("(%d, %d)\n", z.X, z.Y);
            if(col[z.X])
            {
                if(col[z.X] != z.Y)
                {
                    puts("0"); return 0;
                }
                else continue;
            }
            col[z.X] = z.Y;
            for(auto v : adj[z.X])
            {
                q.push(ii(v, -z.Y));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
port_facility.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d %d", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~~

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