Submission #227632

#	Time	Username	Problem	Language	Result	Execution time	Memory
227632		MKopchev	Port Facility (JOI17_port_facility)	C++14	100 / 100	2069 ms	163936 KiB

port_facility

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

const int nmax=1e6+42,mod=1e9+7;

int n;

int parent[nmax];

int root(int node)
{
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

vector<int> adj[nmax];

int group[nmax];

void dfs(int node,int colour)
{
    if(group[node]==-1)group[node]=colour;
    else if(group[node]==colour)return;
    else
    {
        printf("0\n");
        exit(0);
    }

    for(auto k:adj[node])
        dfs(k,!colour);
}

void my_merge(int u,int v)
{
    //cout<<"my_merge "<<u<<" "<<v<<endl;

    adj[u].push_back(v);
    adj[v].push_back(u);

    u=root(u);
    v=root(v);

    parent[v]=u;
}

pair<int,int> inp[nmax];

stack< pair<int,int> > active[2];

bool simulate()
{
    for(int i=1;i<=n;i++)
    {
        int id=group[i];

        while(active[id].size()&&active[id].top().second<inp[i].first)active[id].pop();

        if(active[id].size()&&active[id].top().second<inp[i].second)return 0;

        active[id].push(inp[i]);
    }
    return 1;
}

set< pair<int/*right*/,int/*id*/> > builder;

int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i%i",&inp[i].first,&inp[i].second);

    for(int i=1;i<=n;i++)group[i]=-1,parent[i]=i;

    sort(inp+1,inp+n+1);

    for(int i=1;i<=n;i++)
    {
        pair<int/*right*/,int/*id*/> cur={inp[i].second,i};

        //cout<<"inp: "<<inp[i].first<<" "<<inp[i].second<<endl;

        set< pair<int/*right*/,int/*id*/> >::iterator low=builder.lower_bound({inp[i].first,0}),up=builder.upper_bound({inp[i].second,nmax*2});

        if(low!=up)
        {
            up--;
            pair<int/*right*/,int/*id*/> prv=*up;

            //for(int j=1;j<=n;j++)cout<<root(j)<<" ";cout<<endl;

            while(root(i)!=root(prv.second))
            {
                my_merge((*low).second,i);
                low++;
            }
        }

        builder.insert(cur);
    }


    long long outp=1;

    for(int i=1;i<=n;i++)
        if(root(i)==i)
        {
            outp=outp*2%mod;
            dfs(i,0);
        }

    if(simulate()==0)printf("0\n");
    else printf("%lld\n",outp);

    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
port_facility.cpp:72:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i%i",&inp[i].first,&inp[i].second);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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