oj.uz

Submission #868339

# Submission time Handle Problem Language Result Execution time Memory
868339 2023-10-31T07:40:49 Z josanneo22 Flood (IOI07_flood) C++17
64 / 100
 211 ms 44604 KB 
#pragma warning(disable : 4996)
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(), x.end()
#define orz ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

const int N = 4e5 + 500;
int n, x[N], y[N], to[N][4], dr[N][4], m;
vector<pii> g[N];
int orientation(int a, int b) {
    if (y[a] == y[b]) return x[a] > x[b];
    return 2 + (y[a] > y[b]);
}
void add_edge(int u, int v, int w) {
    g[u].push_back(make_pair(v, w)); 
    g[v].push_back(make_pair(u, w)); 
}
int main() {
    orz;
    cin >> n;
    L(i, 1, n) cin >> x[i] >> y[i];
    cin >> m;
    L(i, 1, m) {
        int u, v; cin >> u >> v;
        dr[u][orientation(u, v)] = dr[v][orientation(v, u)] = i;
        to[u][orientation(u, v)] = v; to[v][orientation(v, u)] = u;
        add_edge(i, i + m, 1);
    }
    L(i, 1, n) {
        vector<int> p;
        if (dr[i][0])p.push_back(0);
        if (dr[i][2])p.push_back(2);
        if (dr[i][1])p.push_back(1);
        if (dr[i][3])p.push_back(3);
        if (p.size() == 0) continue;
        for (int j = 0; j + 1 < p.size(); j++) {
            int u = p[j], v = p[j + 1];
            add_edge(dr[i][u] + (u == 1 || u == 2) * m, dr[i][v] + (v == 0 || v == 3) * m, 0);
        }
        int u = p.back(), v = p.front();
        add_edge(dr[i][u] + (u == 1 || u == 2) * m, dr[i][v] + (v == 0 || v == 3) * m, 0);
    }

    vector<int> vis(N), dis(N, 1E9);
    int S = 0, mxy = -1;
    function<void(int)> dye = [&](int u) {
        vis[u] = true;
        L(i, 0, 3) {
            if (dr[u][i]==0)continue;
            if ((i == 0 || i == 2) && y[u] > mxy) {
                mxy = y[u];  S = dr[u][i];
            }
            if (!vis[to[u][i]]) dye(to[u][i]);
        }
        };
    function<void()> bfs = [&]() {
        deque<int>q;
        q.push_back(S), dis[S] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop_front();
            for (auto& [v, w] : g[u]) {
                if (dis[v] <= dis[u] + w)continue;
                dis[v] = dis[u] + w;
                if (w) q.push_back(v);
                else q.push_front(v);
            }
        }
        };
    L(i, 1, n) {
        if (vis[i]) continue;
        S = 0; mxy = -1; dye(i);
        if (S) bfs();
    }
    int ans = 0;
    L(i, 1, m) ans += (dis[i] != 1E9 && dis[i] == dis[i + m]);
    cout << ans << '\n';
    L(i, 1, m) if (dis[i] == dis[i + m]) cout << i << '\n';
}

Compilation message

flood.cpp:1: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    1 | #pragma warning(disable : 4996)
      | 
flood.cpp: In function 'int main()':
flood.cpp:41:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j + 1 < p.size(); j++) {
      |                         ~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20060 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20060 KB Output is correct

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22104 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 33616 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 32596 KB Output is correct
2 Runtime error 211 ms 44604 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 134 ms 39760 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 183 ms 43668 KB Memory limit exceeded
2 Halted 0 ms 0 KB -