# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
121962 | turbat | Aliens (IOI07_aliens) | 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>
using namespace std;
#define F first
#define S second
#define N 100005
int n, w, k, cnt;
pair <int, int> wall[N][4];
pair <pair <int, int>, int > p[N];
bool vis[2 * N], brok[2 * N], stacked[N];
int dfs(int dir, int u){
if (stacked[u]) return u;
stacked[u] = 1;
int t = dir + 3;
t %= 4;
while (t != (dir + 2) % 4){
if (!vis[wall[u][t].S]) {
vis[wall[u][t].S] = 1;
int cyc = dfs(t, wall[u][t].F);
if (cyc != -1){
brok[wall[u][t].S] = 1;
cnt--;
stacked[u] = 0;
if (cyc != u) return cyc;
}
}
t++;
t %= 4;
}
stacked[u] = 0;
return -1;
}
int main (){
vis[0] = 1;
cin >> n;
for (int i = 1;i <= n;i++) {
p[i].S = i;
cin >> p[i].F.F >> p[i].F.S;
pos[i] = p[i].F;
}
cin >> w;
for (int i = 1;i <= w;i++){
int a, b;
cin >> a >> b;
if (p[a] > p[b]) swap(a, b);
if (p[a].F.F == p[b].F.F){
wall[a][2].F = b, wall[b][0].F = a;
wall[a][2].S = wall[b][0].S = i;
}
else {
wall[a][1].F = b, wall[b][3].F = a;
wall[a][1].S = wall[b][3].S = i;
}
}
sort (p + 1, p + n + 1);
for (int i = 1;i <= n;i++) dfs(1, p[i].S);
cout << w - k<< endl;
for (int i = 1;i <= w;i++)
if (!brok[i])
cout << i << endl;
}