oj.uz

Submission #348795

# Submission time Handle Problem Language Result Execution time Memory
348795 2021-01-15T18:08:52 Z apostoldaniel854 Flood (IOI07_flood) C++14
100 / 100
 160 ms 18080 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 2e5;

struct Edge {
    int to;
    int dir;
    int idx;
};
vector <Edge> gr[1 + MAX_N];
bool active[1 + MAX_N];
int x[1 + MAX_N], y[1 + MAX_N];
int found[1 + MAX_N];

struct Pivot {
    int node;
    int x;
    int idx;
    bool operator < (const Pivot &other) const {
        return x < other.x;
    }
};

Edge find_next (int node, int dir) {
    for (Edge e : gr[node])
        if (active[e.idx] && e.dir == dir)
            return e;
    return {0, 0, 0};
}

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, w;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    cin >> w;
    vector <Pivot> pivots;
    for (int i = 1; i <= w; i++) {
        int a, b;
        cin >> a >> b;
        if (x[a] > x[b] || y[a] > y[b])
            swap (a, b);
        if (x[a] == x[b]) { /// on the same line (horizontal)
            gr[a].pb ({b, 2, i});
            gr[b].pb ({a, 0, i});
            pivots.pb ({a, x[a], i});
        }
        else { /// on the same column (vertical)
            gr[a].pb ({b, 1, i});
            gr[b].pb ({a, 3, i});
        }
        active[i] = true;
    }
    sort (pivots.begin (), pivots.end ());
    for (Pivot pivot : pivots)
        if (active[pivot.idx]) {
            int node = pivot.node;
            int dir = 1;
            vector <int> path;
            do {
                for (int new_dir = dir + 5; new_dir > dir + 1; new_dir--) {
                    Edge new_node = find_next (node, new_dir % 4);
                    if (new_node.to) {
                        dir = new_dir % 4;
                        node = new_node.to;
                        path.pb (new_node.idx);
                        new_dir = 0;
                        found[new_node.idx]++;
                    }
                }
            } while (pivot.node != node);
            for (int x : path)
                active[x] = false;
        }
    vector <int> sol;
    for (int i = 1; i <= w; i++)
        if (found[i] != 1)
            sol.pb (i);
    cout << sol.size () << "\n";
    for (int x : sol)
        cout << x << " ";
    cout << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 5 ms 5100 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6380 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9684 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9664 KB Output is correct
2 Correct 152 ms 16924 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 13092 KB Output is correct
2 Correct 160 ms 18080 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 13856 KB Output is correct
2 Correct 86 ms 12644 KB Output is correct