Submission #861968

#TimeUsernameProblemLanguageResultExecution timeMemory
861968HuyQuang_re_ZeroFlood (IOI07_flood)C++14
100 / 100
198 ms29504 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define N 100005 #define II pair <int,int> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define Log(x) (31-__builtin_clz((int)x)) #define LogLL(x) (63-__builtin_clzll((ll)x)) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) using namespace std; struct point { int x,y; } a[N]; II e[2*N]; int U[N],D[N],L[N],R[N],n,m,i,u,v,mx[N],f[4*N]; bool visited[N]; vector <int> adj[4*N]; int main() { // freopen("flood.inp","r",stdin); // freopen("flood.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y; cin>>m; for(i=1;i<=m;i++) { cin>>u>>v; if(a[u].x>a[v].x || (a[u].x==a[v].x && a[u].y>a[v].y)) swap(u,v); e[i]={ u,v }; if(a[u].x==a[v].x) U[u]=D[v]=i; else R[u]=L[v]=i; } ////////////////////////////////////////////////////////////////////////////////////// auto BFS_point=[&](int u) { queue <int> q; vector <int> vec; int ma=0; q.push(u); visited[u]=1; while(q.size()>0) { int u=q.front(); q.pop(); vec.push_back(u); ma=max(ma,a[u].x); auto consider=[&](int x) { if(x==0) return ; int v=(e[x].fst==u ? e[x].snd : e[x].fst); if(visited[v]) return ; q.push(v); visited[v]=1; }; consider(U[u]); consider(D[u]); consider(L[u]); consider(R[u]); } for(int u:vec) mx[u]=ma; }; for(u=1;u<=n;u++) if(visited[u]==0) BFS_point(u); /////////////////////////////////////////////////////////////////////////////// for(u=1;u<=n;u++) { auto consider=[&](II a,II b) { int u=a.fst+m*(a.snd==1 || a.snd==4),v=b.fst+m*(b.snd==2 || b.snd==3); adj[u].push_back(v); adj[v].push_back(u); }; vector <II> vec; if(U[u]>0) vec.push_back({ U[u],1 }); if(R[u]>0) vec.push_back({ R[u],2 }); if(D[u]>0) vec.push_back({ D[u],3 }); if(L[u]>0) vec.push_back({ L[u],4 }); if(vec.size()==0) continue; if(vec.size()==1) { int u=vec[0].fst,v=vec[0].fst+m; adj[u].push_back(v); adj[v].push_back(u); } else { for(i=1;i<vec.size();i++) consider(vec[i-1],vec[i]); consider(vec.back(),vec[0]); } } set <II> s; memset(f,63,sizeof(f)); for(i=1;i<=m;i++) { int u=e[i].fst,v=e[i].snd; if(a[v].x==mx[v]) { if(a[u].x==a[v].x) s.insert({ 0,i+m }),f[i+m]=0; else if(U[v]==0 && D[v]==0) s.insert({ 0,i }),s.insert({ 0,i+m }),f[i]=f[i+m]=0; } } while(s.size()>0) { int u=s.begin()->snd,v; s.erase(s.begin()); for(int v:adj[u]) if(f[v]>f[u]) { s.erase({ f[v],v }); f[v]=f[u]; s.insert({ f[v],v }); } if(u<=m) v=u+m; else v=u-m; if(f[v]>f[u]+1) { s.erase({ f[v],v }); f[v]=f[u]+1; s.insert({ f[v],v }); } } int res=0; for(i=1;i<=m;i++) res+=(f[i]==f[i+m]); cout<<res<<'\n'; for(i=1;i<=m;i++) if(f[i]==f[i+m]) cout<<i<<'\n'; }

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for(i=1;i<vec.size();i++) consider(vec[i-1],vec[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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...