| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 211952 | tatyam | Flood (IOI07_flood) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
struct wall{
int to, index;
inline bool exist() const { return to + 1; }
};
int main(){
int n;
scanf("%d", &n);
pii p[n];
each(i, p) scanf("%d%d", &i.first, &i.second);
wall g[n][4];
each(i, g) each(j, i) j.to = -1;
int w;
scanf("%d", &w);
rep(w){
int a, b;
scanf("%d%d", &a, &b);
a--; b--;
int d = 0;
if(p[a].first < p[b].first) d = 0;
else if(p[a].first > p[b].first) d = 2;
else if(p[a].second < p[b].second) d = 1;
else d = 3;
g[a][d] = {b, i};
g[b][d ^ 2] = {a, i};
}
vector<bool> ans(w, 1);
vector<pii> visit;
vector<int> sorted(n);
iota(all(sorted), [&](int a, int b){ return p[a] < p[b]; });
int i = 0;
while(true){
while(i < n && all_of(all(g[sorted[i]]), [](const wall& w){ return !w.exist(); })) i++;
if(i == n) break;
int start = sorted[i], at = start, d = 0;
if(!g[at][d].exist()) d = 1;
visit.clear();
do{
if(!g[at][d].exist()){
d++;
d &= 3;
continue;
}
visit.emplace_back(at, d);
ans[g[at][d].index] = !ans[g[at][d].index];
at = g[at][d].to;
d--;
d &= 3;
}while(at != start);
each(i, visit){
const int at = i.first, d = i.second;
if(!g[at][d].exist()) continue;
const int at2 = g[at][d].to, d2 = d ^ 2;
g[at][d].to = -1;
g[at2][d2].to = -1;
}
}
printf("%d\n", accumulate(ans.begin(), ans.end(), 0));
rep(w) if(ans[i]) printf("%d\n", i + 1);
}