Submission #597452

#TimeUsernameProblemLanguageResultExecution timeMemory
597452NekoRollyFlood (IOI07_flood)C++17
60 / 100
313 ms32420 KiB
#include<bits/stdc++.h> using namespace std; #define ff first #define ss second typedef long long ll; typedef pair<int,int> pii; const int N = 1e5+10; const int inf = 1e9; struct Node{ int l,r,x,i; }; struct Rango{ int l,r,i; }; bool operator<(Rango a,Rango b){ return a.l < b.l; } bool operator<(Node a,Node b){ return a.x < b.x; } int n,m; pii p[N]; int Ed[N][4]; vector<pii> adj[N*4]; vector<Node> a1,a2; set<Rango> d; deque<int> d2; int dis[N*4]; vector<int> ans; int Id(int a,int b){ if (p[a].ff == p[b].ff) return p[a].ss < p[b].ss ? 0 : 2; else return p[a].ff < p[b].ff ? 1 : 3; } void Add(int a,int b,int w=0){ adj[a].push_back({b, w}), adj[b].push_back({a, w}); } void new_line(int i,int a,int b){ Ed[a][Id(a, b)] = Ed[b][Id(b, a)] = i; if (Id(a, b) == 0) a1.push_back({p[a].ss, p[b].ss, p[a].ff, i}); if (Id(a, b) == 1) a2.push_back({p[a].ff, p[b].ff, p[a].ss, i}); if (Id(a, b) == 2) a1.push_back({p[b].ss, p[a].ss, p[a].ff, i}); if (Id(a, b) == 3) a2.push_back({p[b].ff, p[a].ff, p[a].ss, i}); } void go(vector<Node> &v){ d.clear(); sort(v.begin(), v.end()); for (auto [l, r, x, i] : v){ auto it = d.upper_bound({l, r, i}); if (d.size() && it != d.begin()){ it--; if (it->r <= l) it++; } vector<Rango> d1; for (; it != d.end() && it->l < r; it++) d1.push_back(*it); for (Rango RL : d1) d.erase(RL); d.insert({l, r, i}); for (Rango RL : d1){ Add(RL.i, i+m); if (RL.l < l) d.insert({RL.l, l, RL.i}); if (r < RL.r) d.insert({r, RL.r, RL.i}); } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i=1; i<=n; i++) cin >> p[i].ff >> p[i].ss; cin >> m; p[++n] = {-1, -1}, p[++n] = {-1, 1e6+1}; p[++n] = {1e6+1, -1}, p[++n] = {1e6+1, 1e6+1}; for (int i=1,a,b; i<=m; i++){ cin >> a >> b; new_line(i, a, b); } m += 4; new_line(m-3, n-3, n-2), new_line(m-2, n-3, n-1); new_line(m-1, n-2, n), new_line(m, n-1, n); for (int i=1; i<=m; i++) Add(i, i+m, 1); for (int i=1; i<=n; i++){ if (Ed[i][0] && Ed[i][1]) Add(Ed[i][0], Ed[i][1]); if (Ed[i][1] && Ed[i][2]) Add(Ed[i][1]+m, Ed[i][2]); if (Ed[i][2] && Ed[i][3]) Add(Ed[i][2]+m, Ed[i][3]+m); if (Ed[i][3] && Ed[i][0]) Add(Ed[i][3], Ed[i][0]+m); } go(a1), go(a2); d.clear(); for (int i=1; i<=2*m; i++) dis[i] = inf; for (int u : {2*m-3, 2*m-2, m-1, m}){ d2.push_back(u); dis[u] = 0;} for (; d2.size(); ){ int u = d2.front(); d2.pop_front(); for (auto [v, w] : adj[u]) if (dis[v] > dis[u] + w){ dis[v] = dis[u] + w; if (w) d2.push_back(v); else d2.push_front(v); } } /* for (int i=1; i<=2*m; i++){ cout << i << " -> "; for (auto [v, w] : adj[i]) if (!w) cout << v << " "; cout << "\n"; } for (int i=1; i<=m; i++) cout << i << " -> " << dis[i] << " " << dis[i+m] << "\n"; */ for (int i=1; i<m-3; i++) if (dis[i] == dis[i+m]) ans.push_back(i); cout << ans.size() << "\n"; for (int x : ans) cout << x << "\n"; return 0; }
#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...