Submission #69261

#	Time	Username	Problem	Language	Result	Execution time	Memory
69261		mirbek01	Port Facility (JOI17_port_facility)	C++17	22 / 100	82 ms	17188 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] <= b[j] && b[j] <= b[i] && a[j] <= a[i] && a[i] <= b[j] || (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;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:19:67: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                   if(a[i] <= b[j] && b[j] <= b[i] && a[j] <= a[i] && a[i] <= b[j] || (a[j] <= b[i] && b[i] <= b[j] && a[i] <= a[j] && a[j] <= b[i])){
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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