| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 410619 |
2021-05-23T07:23:52 Z |
Aldas25 |
Flood (IOI07_flood) |
C++14 |
|
159 ms |
25436 KB |
#pragma GCC target ("avx2")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
const int MAXN = 200100, MAXK = 30;
//const ll MOD = 998244353;
const ll INF = 1e17;
const ld PI = asin(1) * 2;
int n;
int x[MAXN], y[MAXN];
int w;
int a[MAXN], b[MAXN];
unordered_set<int> ans;
int deg[MAXN];
vi avPoints;
bool usedPoint[MAXN];
pii adj[MAXN][4];
bool vis[MAXN][4];
unordered_set<int> curWals;
//vii toEr;
bool cmp (int ida, int idb) {
if (x[ida] != x[idb]) return x[ida] < x[idb];
return y[ida] < y[idb];
}
void dfs (int id, int dir) {
//if (vis[id][dir]) return;
vis[id][dir] = true;
// cout << " dfs in id = " << id << " dir = " << dir << " x = " << x[id] << " y = " << y[id] << endl;
FOR(a, -1, 2) {
int newDir = (dir + a + 4) % 4;
if (adj[id][newDir].f == -1) continue;
int pId = adj[id][newDir].f;
int wId = adj[id][newDir].s;
if (!vis[pId][newDir]) {
if (curWals.count(wId))
ans.insert(wId);
else
curWals.insert(wId);
dfs(pId, newDir);
}
break;
}
}
int main()
{
FAST_IO;
cin >> n;
FOR(i, 1, n) cin >> x[i] >> y[i];
cin >> w;
FOR(i, 1, w) cin >> a[i] >> b[i];
FOR(i, 1, n) avPoints.pb(i);
sort(avPoints.begin(), avPoints.end(), cmp);
FOR(i, 1, n) FOR(d, 0, 3) adj[i][d] = {-1, -1};
FOR(i, 1, w) {
if (x[a[i]] > x[b[i]] || y[a[i]] > y[b[i]]) swap(a[i], b[i]);
if (y[a[i]] == y[b[i]]) {
adj[a[i]][1] = {b[i], i};
adj[b[i]][3] = {a[i], i};
} else {
adj[a[i]][0] = {b[i], i};
adj[b[i]][2] = {a[i], i};
}
deg[a[i]]++;
deg[b[i]]++;
}
for (auto id : avPoints) {
//auto p = *(avPoints.begin());
//int id = p.s;
if (usedPoint[id]) continue;
//toEr.clear();
// cout << " starting walk from id = " << id << " x = " << x[id] << " y = " << y[id] << endl;
curWals.clear();
int stDir = 0;
while (stDir < 3 && vis[id][stDir]) {stDir++;}
dfs (id, stDir);
for (auto i : curWals) {
// int i = wall;
if (y[a[i]] == y[b[i]]) {
adj[a[i]][1].f = -1;
adj[b[i]][3].f = -1;
} else {
adj[a[i]][0].f = -1;
adj[b[i]][2].f = -1;
}
deg[a[i]]--;
deg[b[i]]--;
int id;
id = a[i];
if (deg[id] == 0)
usedPoint[id] = true;
id = b[i];
if (deg[id] == 0)
usedPoint[id] = true;
}
}
cout << (int)ans.size() << "\n";
for (int wall : ans) cout << wall << "\n";
return 0;
}
/*
15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
2320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
9236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
5836 KB |
Output is correct |
| 2 |
Correct |
159 ms |
9660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
9324 KB |
Output is correct |
| 2 |
Correct |
125 ms |
9648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
9620 KB |
Output is correct |
| 2 |
Correct |
154 ms |
25436 KB |
Output is correct |
