Submission #1110601

#TimeUsernameProblemLanguageResultExecution timeMemory
1110601Khalid_AlabdullatifTraffic (CEOI11_tra)C++14
16 / 100
778 ms66376 KiB
#include "bits/stdc++.h" #define ll long long using namespace std; const int N=5e5+1,mod=1e9+7; vector<int>l,r; vector<vector<int>>v(N),rev(N); int n,m,A,B; int x[N],y[N]; bool vis[N],removed[N]; void dfs(int idx){ vis[idx]=1; for(auto i:v[idx]) if(!vis[i] && !removed[i]) dfs(i); } void del(int idx){ vis[idx]=1; for(auto i:v[idx]) if(!vis[i]) del(i); } void delr(int idx){ vis[idx]=1; for(auto i:rev[idx]) if(!vis[i]) delr(i); } int mx[N],mn[N]; int main(){ cin>>n>>m>>A>>B; for(int i=1;i<=n;i++){ cin>>x[i]>>y[i]; if(x[i]==0) l.push_back(i); if(x[i]==A) r.push_back(i); } sort(l.begin(),l.end(),[](int i, int j){ return y[i] < y[j]; }); sort(r.begin(),r.end(),[](int i, int j){ return y[i] < y[j]; }); //reverse(l.begin(),l.end()); while(m--){ int d,c,k; cin>>c>>d>>k; v[c].push_back(d); rev[d].push_back(c); if(k==2){ v[d].push_back(c); rev[c].push_back(d); } } for(auto i:l) del(i); for(int i=1;i<=n;i++) if(!vis[i]) removed[i]=1; memset(vis,0,sizeof vis); for(auto i:r) delr(i); for(int i=1;i<=n;i++) if(!vis[i]) removed[i]=1; for(int i=0;i<r.size();i++) if(removed[r[i]]) r.erase(r.begin()+i); int szl=l.size(),szr=r.size(); memset(vis,0,sizeof vis); int idx=0; for(int i=0;i<szl;i++){ if(removed[l[i]])continue; dfs(l[i]); while(idx+1<szr && vis[r[idx+1]]) idx++; mx[i]=idx; } memset(vis,0,sizeof vis); idx=r.size()-1; for(int i=szl-1;i>=0;i--){ if(removed[l[i]])continue; dfs(l[i]); while(idx-1>=0 && vis[r[idx-1]]) idx--; mn[i]=idx; } vector<int>ans; for(int i=0;i<szl;i++){ if(removed[l[i]]) ans.push_back(0); else ans.push_back(mx[i]-mn[i]+1); } reverse(ans.begin(),ans.end()); for(auto i:ans)cout<<i<<'\n'; return 0; }

Compilation message (stderr)

tra.cpp: In function 'int main()':
tra.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<r.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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...