oj.uz

Submission #349922

# Submission time Handle Problem Language Result Execution time Memory
349922 2021-01-18T17:28:43 Z Sara Flood (IOI07_flood) C++14
73 / 100
 99 ms 28320 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 + 5;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;
 
int n, W;
struct Point{
    int x, y;
} p[N];
inline bool cmp(Point a, Point b){
    return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
vector < pair <int, bool> > g[2 * N];
int in[4][N];
vector < pair <int, int> > nodes;
bool mrk[2 * N];
int h[2 * 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();
        mrk[v] = 1;
        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 + 2 * N, INF);
    for (auto i : nodes){
        if (!mrk[i.S]){
            bfs(i.S);
        }
    }
    print();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8684 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16100 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 16996 KB Output is correct
2 Runtime error 84 ms 28260 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 84 ms 28320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 28260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -