oj.uz

Submission #172662

# Submission time Handle Problem Language Result Execution time Memory
172662 2020-01-02T09:56:31 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 489 ms 233104 KB 
/*
APIO 2017 Rainbow
- We can view a rectangle as a planar graph
    - Put temporary rivers on the outside of the rectangle
    - Each river segment is a node and adjacent rivers constitute an edge
- This problem then becomes finding the number of faces of a planar graph
- We can solve this with Euler's formula
- By Euler's formula, we have
    F = E - V + 1 + C
  where F is faces, E is edges, V is vertices, and C is the number of components
- Each corner of a square is a vertex and each side of a square is an edge if it has a river
*/
 
#include "rainbow.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

int cnt = 1, segtree[4040404], left_c[4040404], right_c[4040404];

struct Segtree {
    set<int> data[202020];
    int roots[202020];

    void add(int x, int y) { data[x].insert(y); }

    void build() {
        FOR(i, 1, 200001) {
            roots[i + 1] = roots[i];
            for (int j : data[i]) update(j, roots[i + 1]);
        }
    }

    void update(int pos, int &node, int l = 1, int r = 200000) {
        segtree[cnt] = segtree[node] + 1;
        left_c[cnt] = left_c[node];
        right_c[cnt] = right_c[node];
        node = cnt++;

        if (l == r) return;
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, right_c[node], mid + 1, r);
        else update(pos, left_c[node], l, mid);
    }

    int query(int l1, int r1, int l2, int r2) {
        if (l2 > r2) return 0;
        return query(l2, r2, roots[r1 + 1], 1, 200000) - query(l2, r2, roots[l1], 1, 200000);
    }
    int query(int a, int b, int node, int l, int r) {
        if (a > r || b < l) return 0;
        if (a <= l && b >= r) return segtree[node];
        int mid = (l + r) / 2;
        return query(a, b, left_c[node], l, mid) + query(a, b, right_c[node], mid + 1, r);
    }
} vertices, edges_horiz, edges_vert, rivers;

int mx_r, mn_r, mx_c, mn_c;
 
void add_river(int x, int y) {
    vertices.add(x, y);
    vertices.add(x + 1, y);
    vertices.add(x, y + 1);
    vertices.add(x + 1, y + 1);
    edges_horiz.add(x, y);
    edges_horiz.add(x + 1, y);
    edges_vert.add(x, y);
    edges_vert.add(x, y + 1);
    rivers.add(x, y);
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
    add_river(sr, sc);
    mx_r = mn_r = sr;
    mx_c = mn_c = sc;
    FOR(i, 0, M) {
        if (S[i] == 'N') sr--;
        if (S[i] == 'E') sc++;
        if (S[i] == 'S') sr++;
        if (S[i] == 'W') sc--;
        add_river(sr, sc);
        mx_r = max(mx_r, sr);
        mn_r = min(mn_r, sr);
        mx_c = max(mx_c, sc);
        mn_c = min(mn_c, sc);
    }
    vertices.build();
    edges_horiz.build();
    edges_vert.build();
    rivers.build();
}
 
int colour(int ar, int ac, int br, int bc) {
    int E = edges_horiz.query(ar + 1, br, ac, bc) + edges_vert.query(ar, br, ac + 1, bc);
    int V = vertices.query(ar + 1, br, ac + 1, bc);
    int R = rivers.query(ar, br, ac, bc);
    int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
    return E - V + C - R;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41720 KB Output is correct
2 Correct 50 ms 42744 KB Output is correct
3 Correct 48 ms 41720 KB Output is correct
4 Correct 48 ms 41848 KB Output is correct
5 Correct 51 ms 43000 KB Output is correct
6 Correct 44 ms 41464 KB Output is correct
7 Correct 45 ms 41484 KB Output is correct
8 Correct 45 ms 41592 KB Output is correct
9 Correct 46 ms 41464 KB Output is correct
10 Correct 44 ms 41464 KB Output is correct
11 Correct 48 ms 42232 KB Output is correct
12 Correct 50 ms 42360 KB Output is correct
13 Correct 51 ms 43556 KB Output is correct
14 Correct 53 ms 44024 KB Output is correct
15 Correct 45 ms 41464 KB Output is correct
16 Correct 44 ms 41472 KB Output is correct
17 Correct 43 ms 41464 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 41472 KB Output is correct
2 Correct 43 ms 41464 KB Output is correct
3 Runtime error 356 ms 209400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 41464 KB Output is correct
2 Runtime error 489 ms 233104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41720 KB Output is correct
2 Correct 50 ms 42744 KB Output is correct
3 Correct 48 ms 41720 KB Output is correct
4 Correct 48 ms 41848 KB Output is correct
5 Correct 51 ms 43000 KB Output is correct
6 Correct 44 ms 41464 KB Output is correct
7 Correct 45 ms 41484 KB Output is correct
8 Correct 45 ms 41592 KB Output is correct
9 Correct 46 ms 41464 KB Output is correct
10 Correct 44 ms 41464 KB Output is correct
11 Correct 48 ms 42232 KB Output is correct
12 Correct 50 ms 42360 KB Output is correct
13 Correct 51 ms 43556 KB Output is correct
14 Correct 53 ms 44024 KB Output is correct
15 Correct 45 ms 41464 KB Output is correct
16 Correct 44 ms 41472 KB Output is correct
17 Correct 43 ms 41464 KB Output is correct
18 Runtime error 302 ms 205688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41720 KB Output is correct
2 Correct 50 ms 42744 KB Output is correct
3 Correct 48 ms 41720 KB Output is correct
4 Correct 48 ms 41848 KB Output is correct
5 Correct 51 ms 43000 KB Output is correct
6 Correct 44 ms 41464 KB Output is correct
7 Correct 45 ms 41484 KB Output is correct
8 Correct 45 ms 41592 KB Output is correct
9 Correct 46 ms 41464 KB Output is correct
10 Correct 44 ms 41464 KB Output is correct
11 Correct 48 ms 42232 KB Output is correct
12 Correct 50 ms 42360 KB Output is correct
13 Correct 51 ms 43556 KB Output is correct
14 Correct 53 ms 44024 KB Output is correct
15 Correct 45 ms 41464 KB Output is correct
16 Correct 44 ms 41472 KB Output is correct
17 Correct 43 ms 41464 KB Output is correct
18 Runtime error 302 ms 205688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -