제출 #348789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348789		apostoldaniel854	Flood (IOI07_flood)	C++14	22 / 100	173 ms	16672 KiB

flood

#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, 3, i});
            gr[b].pb ({a, 1, 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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 3 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9