Submission #1062321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062321		sleepntsheep	Port Facility (JOI17_port_facility)	C++14	22 / 100	30 ms	16516 KiB

port_facility

#include <stdio.h>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=2005;
int n,a[N],b[N];
vector<int>g[N];

int cut(int i, int j){
  return (a[i]<a[j] and b[i] > a[j] and b[i]<b[j])
    or(a[j]<a[i] and b[j]>a[i] and b[j]<b[i]);
}


int main() {
  scanf("%d",&n);
  for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i);
  for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(cut(i,j)){
    g[i].push_back(j);
  }

  int comp{};
  vector<int>col(n),pw2(1+n);
  pw2[0]=1;for(int i=1;i<=n;++i)pw2[i]=pw2[i-1]*2%1000000007;
  for(int i=0;i<n;++i){
    if(col[i])continue;
    queue<int>q;
    q.push(i);col[i]=1;
    while(q.size()){
      auto u=q.front();q.pop();
      for(auto v:g[u])
        if(0==col[v])col[v]=col[u]==1?2:1,q.push(v);
        else if(col[v]==col[u]) return 0*puts("0");
    }
    ++comp;
  }
  printf("%d\n",pw2[comp]);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
port_facility.cpp:19:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i);
      |                       ~~~~~^~~~~~~~~~~~~~~~

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