| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 152545 | stefdasca | Flood (IOI07_flood) | C++14 | 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.
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
using namespace std;
vector<pair<pair<int, int>, int> >v;
multiset<pair<pair<int, int>, int > >ms;
int n, m;
vector<pair<int, int> >mch[100005][5];
bool viz[100005];
vector<int> ans;
pr p[100005];
int direction(pair<int, int> a, pair<int, int> b)
{
if(b.fi == a.fi)
{
if(b.se > a.se)
return 0;
return 2;
}
if(b.fi > a.fi)
return 1;
return 3;
}
int go(int nod, int dir)
{
if (viz[nod])
return nod;
viz[nod] = 1;
for(int i = 0; i < 4; ++i)
{
int nxt = ((dir + 1) - i + 4) % 4;
if(mch[nod][nxt].empty())
continue;
auto ed = mch[nod][nxt].front();
mch[nod][nxt].clear();
int vecin = ed.y;
mch[vecin][(nxt + 2) % 4].clear();
int loop = go(vecin, nxt);
if(!loop)
{
ans.pb(ed.x);
continue;
}
if (loop != nod)
{
viz[nod] = 0;
return loop;
}
}
viz[nod] = 0;
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> p[i].fi >> p[i].se;
v.pb({p[i], i});
}
cin >> m;
for(int i = 1; i <= m; ++i)
{
int a, b;
cin >> a >> b;
mch[a][direction(p[a], p[b])].pb({i, b});
mch[b][direction(p[b], p[a])].pb({i, a});
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); ++i)
go(v[i].se, 0);
cout << ans.size() << '\n';
for(int i = 0; i < ans.size(); ++i)
cout << ans[i] << '\n';
return 0;
}