Submission #861927

#TimeUsernameProblemLanguageResultExecution timeMemory
861927HuyQuang_re_ZeroFlood (IOI07_flood)C++14
64 / 100
292 ms49876 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define N 400005 #define II pair <ll,ll> #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 edge { int num; short int type; }; vector <edge> adj[400005]; struct point { int x,y; } a[100005]; pair <int,int> e[200005]; int n,m,i,u,v,nangle,f[N],mx[100005],ok,alone[100005]; bool visited[100005]; vector <int> angle_to_side[200005][2]; 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 }; adj[u].push_back({ v,0 }); adj[v].push_back({ u,0 }); } auto BFS_point=[&](int u) { queue <int> q; vector <int> node; int ma=0; q.push(u); visited[u]=1; while(q.size()>0) { int u=q.front(); q.pop(); ma=max(ma,a[u].x); node.push_back(u); for(edge x:adj[u]) if(visited[x.num]==0) q.push(x.num),visited[x.num]=1; } for(int u:node) mx[u]=ma; }; for(u=1;u<=n;u++) if(visited[u]==0) BFS_point(u); for(u=1;u<=n;u++) adj[u].clear(); for(i=1;i<=m;i++) { int u=e[i].fst,v=e[i].snd; if(a[v].x>a[u].x) adj[u].push_back({ i,2 }),adj[v].push_back({ i,4 }); if(a[v].y>a[u].y) adj[u].push_back({ i,1 }),adj[v].push_back({ i,3 }); } for(u=1;u<=n;u++) { sort(adj[u].begin(),adj[u].end(),[&](edge a,edge b){ return a.type<b.type; }); if(adj[u].size()==0) continue; else if(adj[u].size()==1) { edge x=adj[u].back(); alone[u]=++nangle; for(i=0;i<=1;i++) angle_to_side[x.num][i].push_back(nangle); } else { auto consider=[&](edge a,edge b) { int oka=(a.type==1 || a.type==4),okb=(b.type==2 || b.type==3); nangle++; angle_to_side[a.num][oka].push_back(nangle); angle_to_side[b.num][okb].push_back(nangle); }; for(i=1;i<adj[u].size();i++) consider(adj[u][i-1],adj[u][i]); consider(adj[u].back(),adj[u][0]); } } for(u=1;u<=n;u++) adj[u].clear(); for(i=1;i<=m;i++) { for(ok=0;ok<=1;ok++) { u=angle_to_side[i][ok][0],v=angle_to_side[i][ok][1]; adj[u].push_back({ v,0 }),adj[v].push_back({ u,0 }); } u=angle_to_side[i][0][0],v=angle_to_side[i][1][0]; adj[u].push_back({ v,1 }),adj[v].push_back({ u,1 }); } memset(f,63,sizeof(f)); set <pair <int,int> > s; 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) for(int u:angle_to_side[i][1]) s.insert({ 0,u }),f[u]=0; else if(alone[v]>0) s.insert({ 0,alone[v] }),f[alone[v]]=0; } } while(s.size()>0) { int u=s.begin()->snd; s.erase(s.begin()); for(edge x:adj[u]) { int v=x.num,k=x.type; if(f[v]>f[u]+k) { s.erase({ f[v],v }); f[v]=f[u]+k; s.insert({ f[v],v }); } } } int res=0; for(i=1;i<=m;i++) { int u=angle_to_side[i][0][0],v=angle_to_side[i][1][0]; if(f[u]==f[v]) res++; } cout<<res<<'\n'; for(i=1;i<=m;i++) { int u=angle_to_side[i][0][0],v=angle_to_side[i][1][0]; if(f[u]==f[v]) cout<<i<<'\n'; } }

Compilation message (stderr)

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