Submission #44590

#	Time	Username	Problem	Language	Result	Execution time	Memory
44590		smu201111192	Port Facility (JOI17_port_facility)	C++17	0 / 100	44 ms	51192 KiB

port_facility

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 1000005;
int n,color[MAXN],vis[MAXN];
pair<int,int> seg[MAXN];
vector<int> same[MAXN],diff[MAXN];
const int mod = 1e9+7;
void dfs(int here,int c){
    color[here] = c;
    for(int i = 0; i < same[here].size(); i++){
        int there = same[here][i];
        if(color[there]!= -1 && color[there] != c){
            cout<<0; exit(0);
        }
        else if(color[there] == -1) dfs(there,c);
    }
    for(int i = 0; i < diff[here].size(); i++){
        int there = diff[here][i];
        if(color[there] != -1 && color[there] == c){
            cout<<0; exit(0);
        }
        else if(color[there] == -1)dfs(there,c^1);
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1; i <=n; i++){
        cin >> seg[i].first >> seg[i].second;
    }
    sort(seg+1,seg+n+1);
    set<pair<int,int> > stk;
    int ccn = 0;
    for(int i = 1; i <= n; i++){
        while(stk.size() && stk.begin()->first < seg[i].first) stk.erase(stk.begin());
        vector<int> vc;
        for(auto it = stk.begin(); it!= stk.end(); it++){
            if(it->first > seg[i].second) break;
            vc.push_back(it->second);
        }
        for(int i = 0; i < (int)vc.size() - 1; i++){
            int id1 = vc[i];
            int id2 = vc[i+1];
            same[id1].push_back(id2);
            same[id2].push_back(id1);
            stk.erase(make_pair(seg[id1].second,id1));
        }
        if(vc.size()){
            diff[vc.back()].push_back(i);
            diff[i].push_back(vc.back());
        }
        stk.insert(make_pair(seg[i].second,i));
    }
    memset(color,-1,sizeof(color));
    long long ans = 1;
    for(int i = 1; i <= n; i++){
        if(color[i] == -1){
            dfs(i,0);
            ccn++;
        }
    }
    for(int i = 0; i < ccn; i++){
        ans *= 2;
        ans %= mod;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void dfs(int, int)':
port_facility.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < same[here].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < diff[here].size(); i++){
                    ~~^~~~~~~~~~~~~~~~~~~

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