oj.uz

Submission #1054287

# Submission time Handle Problem Language Result Execution time Memory
1054287 2024-08-12T08:25:35 Z 정민찬(#11058) Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 28 ms 31324 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

int r, c;
vector<int> vis[200010];
vector<pair<int,int>> ran[200010];

void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R;
    c = C;
    int x = sr, y = sc;
    vis[x].push_back(y);
    for (int i=0; i<M; i++) {
        if (S[i] == 'N') x --;
        if (S[i] == 'S') x ++;
        if (S[i] == 'W') y --;
        if (S[i] == 'E') y ++;
        vis[x].push_back(y);
    }
    for (int i=1; i<=R; i++) {
        sort(vis[i].begin(), vis[i].end());
        vis[i].erase(unique(vis[i].begin(), vis[i].end()), vis[i].end());
        int p = 0;
        for (auto &y : vis[i]) {
            if (y != p + 1) {
                ran[i].push_back({p+1, y-1});
            }
            p = y;
        }
        if (p != C) ran[i].push_back({p+1, C});
    }
}

struct DisjointSet{
    vector<int> par;
    void init(int n) {
        par.resize(n);
        iota(par.begin(), par.end(), 0);
    }
    int Find(int x) {
        if (par[x] == x) return x;
        return par[x] = Find(par[x]);
    }
    void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        par[y] = x;
    }
};

DisjointSet dsu;

vector<array<int,3>> ran2[200010];

int colour(int ar, int ac, int br, int bc) {
    int num = 0;
    for (int x=ar; x<=br; x++) {
        for (auto &[ly, ry] : ran[x]) {
            if (ry < ac) continue;
            if (ly > bc) break;
            int nly = max(ly, ac);
            int nry = min(ry, bc);
            ran2[x].push_back({nly, nry, num++});
        }
    }
    dsu.init(num);
    for (int x=ar+1; x<=br; x++) {
        if (ran2[x].empty() || ran2[x-1].empty()) continue;
        int j = 0;
        for (auto &[ly, ry, id] : ran2[x]) {
            while (j < ran2[x-1].size() && ran2[x-1][j][1] <= ry) {
                if (ran2[x-1][j][1] >= ly) dsu.Union(ran2[x-1][j][2], id);
                j ++;
            }
            if (j < ran2[x-1].size() && ry >= ran2[x-1][j][0]) {
                dsu.Union(ran2[x-1][j][2], id);
            }
        }
    }
    int ans = 0;
    for (int x=ar; x<=br; x++) {
        for (auto &[ly, ry, id] : ran2[x]) {
            if (dsu.Find(id) == id)
                ans ++;
        }
    }
    return ans;
}
/*
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}*/

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:60:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for (auto &[ly, ry] : ran[x]) {
      |                    ^
rainbow.cpp:72:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         for (auto &[ly, ry, id] : ran2[x]) {
      |                    ^
rainbow.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while (j < ran2[x-1].size() && ran2[x-1][j][1] <= ry) {
      |                    ~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             if (j < ran2[x-1].size() && ry >= ran2[x-1][j][0]) {
      |                 ~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:84:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |         for (auto &[ly, ry, id] : ran2[x]) {
      |                    ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 14828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 14428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14428 KB Output is correct
2 Correct 14 ms 24596 KB Output is correct
3 Correct 17 ms 25948 KB Output is correct
4 Correct 15 ms 24412 KB Output is correct
5 Correct 15 ms 24316 KB Output is correct
6 Correct 21 ms 26456 KB Output is correct
7 Correct 25 ms 27228 KB Output is correct
8 Correct 5 ms 15320 KB Output is correct
9 Correct 5 ms 15448 KB Output is correct
10 Correct 8 ms 18012 KB Output is correct
11 Correct 9 ms 18648 KB Output is correct
12 Correct 11 ms 21836 KB Output is correct
13 Correct 16 ms 24412 KB Output is correct
14 Correct 14 ms 22876 KB Output is correct
15 Correct 13 ms 22996 KB Output is correct
16 Correct 19 ms 25972 KB Output is correct
17 Correct 16 ms 24412 KB Output is correct
18 Correct 17 ms 25732 KB Output is correct
19 Correct 16 ms 26836 KB Output is correct
20 Correct 14 ms 25304 KB Output is correct
21 Correct 5 ms 15480 KB Output is correct
22 Correct 6 ms 15708 KB Output is correct
23 Correct 12 ms 21596 KB Output is correct
24 Correct 15 ms 22760 KB Output is correct
25 Correct 20 ms 28436 KB Output is correct
26 Correct 26 ms 31324 KB Output is correct
27 Correct 24 ms 29664 KB Output is correct
28 Correct 26 ms 29900 KB Output is correct
29 Correct 28 ms 28540 KB Output is correct
30 Correct 28 ms 28760 KB Output is correct
31 Correct 24 ms 30036 KB Output is correct
32 Correct 20 ms 29648 KB Output is correct
33 Correct 20 ms 29568 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 14828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 14828 KB Output isn't correct
2 Halted 0 ms 0 KB -