| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 351158 |
2021-01-19T13:13:11 Z |
minoum |
Flood (IOI07_flood) |
C++17 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int MAXN = 5e5 + 10;
int n, m, h[MAXN], dw[MAXN], up[MAXN], lf[MAXN], ri[MAXN], allw[MAXN];
vector <pair<int,int>> pt, adj[MAXN], ofo, amo, w; //ofo=y,amo=x
bool visit[MAXN];
inline void addedge(){
for(int i = 0; i < n; i++){
if(allw[i] <= 1) continue;
if(up[i] != -1 && ri[i] != -1){
adj[up[i]*2].push_back({ri[i]*2+1,0});
adj[ri[i]*2+1].push_back({up[i]*2,0});
if(dw[i]==-1&&lf[i]==-1){
adj[up[i]*2+1].push_back({ri[i]*2,0});
adj[ri[i]*2].push_back({up[i]*2+1,0});
}
}
if(dw[i] != -1 && ri[i] != -1){
adj[dw[i]*2].push_back({ri[i]*2,0});
adj[ri[i]*2].push_back({dw[i]*2,0});
if(lf[i]==-1 && up[i]==-1){
adj[dw[i]*2+1].push_back({ri[i]*2+1,0});
adj[ri[i]*2+1].push_back({dw[i]*2+1,0});
}
}
if(dw[i] != -1 && lf[i] != -1){
adj[dw[i]*2+1].push_back({lf[i]*2,0});
adj[lf[i]*2].push_back({dw[i]*2+1,0});
if(up[i]==-1&&ri[i]==-1){
adj[dw[i]*2].push_back({lf[i]*2+1,0});
adj[lf[i]*2+1].push_back({dw[i]*2,0});
}
}
if(up[i] != -1 && lf[i] != -1){
adj[up[i]*2+1].push_back({lf[i]*2+1,0});
adj[lf[i]*2+1].push_back({up[i]*2+1,0});
if(dw[i]==-1&&ri[i]==-1){
adj[up[i]*2].push_back({lf[i]*2,0});
adj[lf[i]*2].push_back({up[i]*2,0});
}
}
if(up[i] != -1 && dw[i] != -1){
if(ri[i] == -1){
adj[up[i]*2].push_back({dw[i]*2,0});
adj[dw[i]*2].push_back({up[i]*2,0});
}
if(lf[i] == -1){
adj[up[i]*2+1].push_back({dw[i]*2+1,0});
adj[dw[i]*2+1].push_back({up[i]*2+1,0});
}
}
if(ri[i] != -1 && lf[i] != -1){
if(dw[i] == -1){
adj[ri[i]*2].push_back({lf[i]*2,0});
adj[lf[i]*2].push_back({ri[i]*2,0});
}
if(up[i] == -1){
adj[ri[i]*2+1].push_back({ri[i]*2+1,0});
adj[lf[i]*2+1].push_back({lf[i]*2+1,0});
}
}
}
for(int i = 0; i < m; i++){
int t = 1;
if(allw[w[i].first]==1 || allw[w[i].second]==1) t = 0;
adj[i*2].push_back({i*2+1,t});
adj[i*2+1].push_back({i*2,t});
}
return;
}
inline void bfs(int r){
visit[r] = true; h[r] = 0;
deque <int> q;
q.push_back(r);
while(!q.empty()){
int v = q.front(); q.pop_front(); visit[v] = true;
for(auto i: adj[v]){
int u = i.first, ww = i.second;
if(h[u] <= h[v]+ww) continue;
h[u] = h[v]+ww;
if(ww == 0) q.push_front(u);
else q.push_back(u);
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for(int i = 0; i < MAXN; i++) h[i] = INT_MAX;
cin >> n;
for(int i = 0; i < n; i++){
int xx,yy;
cin >> xx >> yy;
pt.push_back({xx,yy});
dw[i] = up[i] = lf[i] = ri[i] = -1;
}
cin >> m;
for(int i = 0; i < m; i++){
int u, v, t = 0;
cin >> u >> v; u--; v--;
if(pt[u].first==pt[v].first){
t = 1;
amo.push_back({pt[u].first,i});
if(pt[u].second > pt[v].second) swap(u,v);
dw[u] = i; up[v] = i;
}
else{
ofo.push_back({pt[u].second,i});
if(pt[u].first > pt[v].first) swap(u,v);
ri[u] = i; lf[v] = i;
}
allw[u]++; allw[v]++;
w.push_back({u,v});
}
addedge();
sort(ofo.begin(), ofo.end());
sort(amo.begin(), amo.end());
for(auto i: ofo)
if(!visit[i.second*2]) bfs(i.second*2+1);
for(auto i: amo)
if(!visit[i.second*2]) bfs(i.second*2+1);
vector <int> ans;
for(int i = 0; i < m; i++)
if(h[i*2] == h[i*2+1]) ans.push_back(i);
cout << (int)ans.size() << '\n';
for(auto i: ans) cout << i+1 <<'\n';
return 0;
}
Compilation message
flood.cpp: In function 'void bfs(int)':
flood.cpp:78:2: error: reference to 'visit' is ambiguous
78 | visit[r] = true; h[r] = 0;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
from flood.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1649 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
flood.cpp:10:6: note: 'bool visit [500010]'
10 | bool visit[MAXN];
| ^~~~~
flood.cpp:82:37: error: reference to 'visit' is ambiguous
82 | int v = q.front(); q.pop_front(); visit[v] = true;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
from flood.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1649 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
flood.cpp:10:6: note: 'bool visit [500010]'
10 | bool visit[MAXN];
| ^~~~~
flood.cpp: In function 'int main()':
flood.cpp:127:7: error: reference to 'visit' is ambiguous
127 | if(!visit[i.second*2]) bfs(i.second*2+1);
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
from flood.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1649 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
flood.cpp:10:6: note: 'bool visit [500010]'
10 | bool visit[MAXN];
| ^~~~~
flood.cpp:129:7: error: reference to 'visit' is ambiguous
129 | if(!visit[i.second*2]) bfs(i.second*2+1);
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:133,
from flood.cpp:1:
/usr/include/c++/9/variant:1649:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1649 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
flood.cpp:10:6: note: 'bool visit [500010]'
10 | bool visit[MAXN];
| ^~~~~
