oj.uz

Submission #349926

# Submission time Handle Problem Language Result Execution time Memory
349926 2021-01-18T17:41:21 Z Sara Flood (IOI07_flood) C++14
100 / 100
 339 ms 31456 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll unsigned long long
#define F first
#define S second
#define pb push_back
#define pf push_front
 
const ll N = 1e5 + 2;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;
 
int n, W;
struct Point{
    int x, y;
} p[N];

vector < pair <int, bool> > g[4 * N];
int in[4][N];
vector < pair <int, int> > nodes;
int h[4 * N];
int ans;
 
inline void add_edge(int u, int v, bool w){
    g[u].pb({v, w}); g[v].pb({u, w});
    return;
}
 
inline void scan(){
    cin >> n;
    for (int i = 1; i <= n; i ++){
        cin >> p[i].x >> p[i].y;
        for (int j : {0, 1, 2, 3}){
            in[j][i] = -1;
        }
    }
    cin >> W;
    for (int i = 1; i <= W; i ++){
        int a, b;
        cin >> a >> b;
        if (p[a].x == p[b].x){
            if (p[b].y < p[a].y) swap(a, b);
            in[2][a] = i; in[0][b] = i;
        }
        else {
            if (p[b].x < p[a].x) swap(a, b);
            in[1][a] = i; in[3][b] = i;
            nodes.pb({p[a].y, 2 * i + 1});
        }
        int u = 2 * i; int v = u + 1;
        add_edge(u, v, 1);
    }
    sort(nodes.begin(), nodes.end());
    return;
}
 
inline void add_edges(){
    for (int i = 1; i <= n; i ++){
        for (int j : {0, 1, 2, 3}){
            if (in[j][i] == -1) continue;
            int k = (j + 1) % 4;
            while (in[k][i] == -1) k = (k + 1) % 4;
            int u = 2 * in[j][i] + (j == 0 || j == 3);
            int v = 2 * in[k][i] + (k == 1 || k == 2);
            add_edge(u, v, 0);  
        }
    }
    return;
}
 
deque <int> d;
inline void bfs(int root){
    d.pb(root); 
    h[root] = 0;
    while (d.size()){
        int v = d.back();
        d.pop_back();
        for (auto i : g[v]){
            int u = i.F, w = i.S;
            if (h[v] + w < h[u]){
                h[u] = h[v] + w;
                if (w) d.pf(u);
                else   d.pb(u);
            }
        }
    }
    return;
}
 
inline void print(){
    for (int i = 1; i <= W; i ++){
        if (h[2 * i] == h[2 * i + 1]){
            ans ++;
        }
    }
    cout << ans << '\n';
    for (int i = 1; i <= W; i ++){
        if (h[2 * i] == h[2 * i + 1]){
            cout << i << '\n';
        }
    }
    return;
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    scan();
    add_edges();
    fill(h, h + 4 * N, INF);
    for (auto i : nodes){
        if (h[i.S] == INF){
            bfs(i.S);
        }
    }
    print();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11372 KB Output is correct
2 Correct 8 ms 11372 KB Output is correct
3 Correct 7 ms 11372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11372 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11372 KB Output is correct
2 Correct 8 ms 11372 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11372 KB Output is correct
2 Correct 7 ms 11380 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11372 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11372 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 8 ms 11372 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11372 KB Output is correct
2 Correct 8 ms 11372 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14188 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 21476 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 22396 KB Output is correct
2 Correct 316 ms 30944 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 28296 KB Output is correct
2 Correct 339 ms 31456 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 30804 KB Output is correct
2 Correct 221 ms 26848 KB Output is correct