Submission #27121

#	Time	Username	Problem	Language	Result	Execution time	Memory
27121		samir_droubi	Port Facility (JOI17_port_facility)	C++14	22 / 100	3349 ms	818728 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
int n;
const int mxn=(1e6)+5;
pair<int,int>a[mxn];

int mod=(1e9)+7;
map<int,int>in;
vector<int>gr[mxn];
int vis[mxn];
int ans=1;
queue<int>q;
void bfs()
{
  while(!q.empty())
  {
    int v=q.front();
    q.pop();
    for(int i=0;i<gr[v].size();++i)
    {
      int u=gr[v][i];
      if(vis[v]==vis[u])
        ans=0;
      if(vis[u]==-1)
      {
        vis[u]=1-vis[v];
        q.push(u);
      }
    }
  }
}
int main()
{
  memset(vis,-1,sizeof vis);

  scanf("%d",&n);
  for(int i=1;i<=n;++i)
    scanf("%d%d",&a[i].first,&a[i].second);
  sort(a+1,a+n+1);
  
  for(int i=1;i<=n;++i)
  {
    map<int,int>::iterator it=in.lower_bound(a[i].first);
    for(it;it!=in.end()&&(it->first)<a[i].second;++it)
    {
      gr[i].push_back(it->second);
      gr[it->second].push_back(i);
    }
    in[a[i].second]=i;
  }

  for(int i=1;i<=n;++i)
  {
    if(vis[i]!=-1)continue;
    vis[i]=0;
    q.push(i);
    bfs();
    ans*=2;
    ans%=mod;
  }
  printf("%d\n",ans);
  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void bfs()':
port_facility.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[v].size();++i)
                  ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:44:11: warning: statement has no effect [-Wunused-value]
     for(it;it!=in.end()&&(it->first)<a[i].second;++it)
           ^
port_facility.cpp:36:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
port_facility.cpp:38:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&a[i].first,&a[i].second);
                                           ^

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