Submission #190740

#	Time	Username	Problem	Language	Result	Execution time	Memory
190740		rkm0959	Port Facility (JOI17_port_facility)	C++14	100 / 100	3242 ms	227604 KiB

port_facility

#include <bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long double ldb;
typedef long long int ll;
typedef unsigned long long int ull;
typedef complex<double> base;
ll mod=1e9+7;

vector<int> must_equal[1111111];
int fuck[1111111], n, cur, cnt;
int indx[2222222];
pair<int, int> a[1111111];
int vis[1111111], vis_2[1111111];
int whi[1111111], col[1111111];
vector<int> con[1111111];
set<int> S, ALV; bool pos=true;
set<int>::iterator it, itp;
queue<int> Q;

void merge(int idx, int L, int R) // [L, R] merge
{
    it=ALV.lower_bound(L);
    if(it!=ALV.end() && (*it)<=R) { fuck[idx]=indx[(*it)]; }
    it=S.lower_bound(L); int myloc, yourloc;
    while(1)
    {
        if(it==S.end()) break; myloc=(*it);
        itp=ALV.upper_bound(myloc);
        if(itp==ALV.end() || (*itp)>R) break;
        yourloc=(*itp);
        must_equal[indx[myloc]].push_back(indx[yourloc]);
        must_equal[indx[yourloc]].push_back(indx[myloc]);
        // now connect (*it) and (*itp)
        it=S.erase(it);
    }
}

void bfs(int x)
{
    whi[x]=cur; vis[x]=1; Q.push(x);
    while(!Q.empty())
    {
        int wow=Q.front(); Q.pop();
        for(int i=0 ; i<must_equal[wow].size() ; i++)
        {
            int nxt=must_equal[wow][i];
            if(!vis[nxt]) { whi[nxt]=cur; vis[nxt]=1; Q.push(nxt); }
        }
    }
}

void bfs_2(int x)
{
    col[x]=1; vis_2[x]=1; Q.push(x);
    while(!Q.empty())
    {
        int wow=Q.front(); Q.pop();
        for(int i=0 ; i<con[wow].size() ; i++)
        {
            int nxt=con[wow][i];
            if(vis_2[nxt] && col[nxt]+col[wow]!=3) pos=false;
            if(!vis_2[nxt]) { col[nxt]=3-col[wow]; vis_2[nxt]=1; Q.push(nxt); }
        }
    }
}

int main(void)
{
    fio; int i; cin>>n;
    for(i=1 ; i<=n ; i++) cin>>a[i].first>>a[i].second;
    sort(a+1, a+n+1);
    for(i=1 ; i<=n ; i++) indx[a[i].first]=i, indx[a[i].second]=i;
    for(i=1 ; i<=n ; i++)
    {
        merge(i, a[i].first+1, a[i].second-1);
        S.insert(a[i].second); ALV.insert(a[i].second);
    }
    for(i=1 ; i<=n ; i++) if(!vis[i]) { cur++; bfs(i); }
    for(i=1 ; i<=n ; i++)
    {
        if(fuck[i])
        {
            con[whi[fuck[i]]].push_back(whi[i]);
            con[whi[i]].push_back(whi[fuck[i]]);
        }
    }
    for(i=1 ; i<=cur ; i++) if(!vis_2[i]) { cnt++; bfs_2(i); }
    ll ans=1; for(i=1 ; i<=cnt ; i++) ans=(2*ans)%mod;
    if(pos) cout<<ans; 
    else cout<<0; return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void merge(int, int, int)':
port_facility.cpp:28:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(it==S.end()) break; myloc=(*it);
         ^~
port_facility.cpp:28:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if(it==S.end()) break; myloc=(*it);
                                ^~~~~
port_facility.cpp: In function 'void bfs(int)':
port_facility.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<must_equal[wow].size() ; i++)
                       ~^~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'void bfs_2(int)':
port_facility.cpp:59:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<con[wow].size() ; i++)
                       ~^~~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:91:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
     else cout<<0; return 0;
     ^~~~
port_facility.cpp:91:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
     else cout<<0; return 0;
                   ^~~~~~

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