oj.uz

답안 #410619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410619 2021-05-23T07:23:52 Z Aldas25 Flood (IOI07_flood) C++14
100 / 100
 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

*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 412 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2320 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 9236 KB Output is correct

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 5836 KB Output is correct
2 Correct 159 ms 9660 KB Output is correct

Subtask #13
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 9324 KB Output is correct
2 Correct 125 ms 9648 KB Output is correct

Subtask #14
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 9620 KB Output is correct
2 Correct 154 ms 25436 KB Output is correct