Submission #135007

#	Time	Username	Problem	Language	Result	Execution time	Memory
135007		mirbek01	Port Facility (JOI17_port_facility)	C++11	22 / 100	65 ms	16632 KiB

port_facility

# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e3 + 2;
 
int n, a[N], b[N], col[N], ans;
vector <int> g[N];
 
int main(){
      cin >> n;
 
      for(int i = 1; i <= n; i ++){
            cin >> a[i] >> b[i];
      }
		
	  for(int i = 1; i <= n; i ++){
    	  for(int j = i + 1; j <= n; j ++){
			  if(a[i] > a[j])
				  swap(a[i], a[j]), swap(b[i], b[j]); 
		  }	
	  }
	  
      for(int i = 1; i <= n; i ++){
            for(int j = i + 1; j <= n; j ++){
                  if(a[j] <= b[i] && b[i] <= b[j] && a[i] <= a[j] && a[j] <= b[i]){
                        g[i].push_back(j);
                        g[j].push_back(i);
                  }
            }
      }
 
      bool ok = 1;
      int cnt = 0;
 
      for(int i = 1; i <= n; i ++){
            if(!col[i]){
                  cnt ++;
                  queue <int> q;
                  col[i] = 1;
                  q.push(i);
                  while(!q.empty()){
                        int v = q.front();
                        q.pop();
                        for(int to : g[v]){
                              if(!col[to]){
                                    col[to] = 3 - col[v];
                                    q.push(to);
                              } else {
                                    if(col[v] == col[to])
                                          ok = 0;
                              }
                        }
                  }
            }
      }
 
      if(!ok){
            puts("0");
            return 0;
      }
 
      int ans = 1, mod = 1e9 + 7;
 
      for(int i = 1; i <= cnt; i ++){
            ans *= 2;
            ans %= mod;
      }
 
      cout << ans << endl;
}

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