Submission #896835

#TimeUsernameProblemLanguageResultExecution timeMemory
896835AiperiiiPort Facility (JOI17_port_facility)C++14
22 / 100
6090 ms33044 KiB
#include <bits/stdc++.h> #define int long long #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back using namespace std; const int mod=1e9+7; signed main(){ ios_base::sync_with_stdio(); cin.tie(0); int n; cin>>n; vector <pair <int,int> > seg(n); vector <vector <int> > v; for(int i=0;i<n;i++){ cin>>seg[i].ff>>seg[i].ss; } sort(all(seg)); for(int i=0;i<n;i++){ v.pb({seg[i].ff,i,0}); v.pb({seg[i].ss,i,1}); } sort(all(v)); vector <int> g[n]; set <pair <int,int> > st; for(int i=0;i<v.size();i++){ if(v[i][2]==0){ int ind=v[i][1]; st.insert({seg[ind].ss,ind}); } else{ auto it=st.lower_bound({v[i][0],v[i][1]}); it++; while(it!=st.end()){ if(it->ff>v[i][0] && it->ss>v[i][1]){ g[v[i][1]].pb(it->ss); g[it->ss].pb(v[i][1]); } it++; } st.erase({v[i][0],v[i][1]}); } } queue <int> q; vector <int> vis(n); int cnt=0; for(int i=0;i<n;i++){ if(!vis[i]){ cnt++; q.push(i); vis[i]=1; while(!q.empty()){ int v=q.front(); q.pop(); for(auto to : g[v]){ if(!vis[to]){ vis[to]=1; q.push(to); } } } } } for(int i=0;i<n;i++)vis[i]=0; bool flag=true; for(int i=0;i<n;i++){ if(!vis[i]){ q.push(i); vis[i]=1; while(!q.empty()){ int v=q.front(); q.pop(); for(auto to : g[v]){ if(!vis[to]){ if(vis[v]==1)vis[to]=2; if(vis[v]==2)vis[to]=1; q.push(to); } else if(vis[to]==vis[v]){ flag=false;break; } } } } } if(flag){ int x=1; for(int i=0;i<cnt;i++){ x*=2; x%=mod; } cout<<x<<"\n"; } else cout<<0<<"\n"; }

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:29:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...