Submission #550759

#	Time	Username	Problem	Language	Result	Execution time	Memory
550759		AJ00	Port Facility (JOI17_port_facility)	C++14	22 / 100	2994 ms	1048576 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
const int MOD = 1e9+7;
pair<int,int> tim[1000001];
vector<int> adj[1000001];
int col[1000001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tc=1,n,q,k,m; 
    //cin >> tc;
    for (int poppo = 1; poppo <= tc; poppo++){
        //cout << "Case #" << poppo << ": "; 
        cin >> n;
        for (int i = 1; i <= n; i++){
            cin >> tim[i].first >> tim[i].second;
            col[i] = -1;
        }
        sort(tim+1,tim+n+1);
        int cur = 1;
        set<pair<int,int>> s;
       // priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 1; i <= (2*n); i++){
            if (i != tim[cur].first){
                s.erase(s.begin());
                continue;
            }
            s.insert({tim[cur].second,cur});
            for (auto const &var: s){
                if (var.first == tim[cur].second){
                    break;
                }
                adj[cur].push_back(var.second);
                adj[var.second].push_back(cur);
            }
            cur++;
        }
        int ans = 1;
        for (int i = 1; i <= n; i++){
            if (col[i] != -1){
                continue;
            }
            col[i] = 1;
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int p = q.front();
                q.pop();
                for (int c: adj[p]){
                    if (col[c] != -1){
                        if (col[c] == col[p]){
                            cout << 0 << "\n";
                            return 0;
                        }
                    }
                    else {
                        col[c] = 1-col[p];
                        q.push(c);
                    }
                }
            }
            ans = ((ans*2)%MOD);
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:12:16: warning: unused variable 'q' [-Wunused-variable]
   12 |     int tc=1,n,q,k,m;
      |                ^
port_facility.cpp:12:18: warning: unused variable 'k' [-Wunused-variable]
   12 |     int tc=1,n,q,k,m;
      |                  ^
port_facility.cpp:12:20: warning: unused variable 'm' [-Wunused-variable]
   12 |     int tc=1,n,q,k,m;
      |                    ^

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