oj.uz

Submission #824147

# Submission time Handle Problem Language Result Execution time Memory
824147 2023-08-13T15:39:49 Z GrindMachine Land of the Rainbow Gold (APIO17_rainbow) C++17
24 / 100
 1205 ms 18800 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "rainbow.h"

struct DSU {
    vector<int> par, rankk, siz;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
    }
};

vector<int> here[N];
vector<pii> row_segs[N];
int n,m;

void init(int n_, int m_, int sr, int sc, int k, char *S) {
    n = n_;
    m = m_;
    here[sr].pb(sc);
    rep(i,k){
        char ch = S[i];
        if(ch == 'E'){
            sc++;
        }
        else if(ch == 'W'){
            sc--;
        }
        else if(ch == 'N'){
            sr--;
        }
        else{
            sr++;
        }
        here[sr].pb(sc);
    }    

    rep1(i,n){
        auto &v = here[i];
        sort(all(v));
        v.resize(unique(all(v))-v.begin());
    }
}

int colour(int ar, int ac, int br, int bc) {
    vector<array<int,3>> prev_segs;
    vector<pii> edges;
    int ptr = 1;

    for(int i = ar; i <= br; ++i){
        vector<array<int,3>> curr_segs;
        auto add = [&](int l, int r){
            if(l <= r){
                curr_segs.pb({l,r,ptr++});
            }
        };

        auto it = lower_bound(all(here[i]),ac);
        if(it == here[i].end() or *it > bc){
            add(ac,bc);
        }
        else{
            add(ac,*it-1);
            int pos = it-here[i].begin();
            int siz = sz(here[i]);

            while(true){
                if(here[i][pos] > bc) break;
                if(pos+1 == siz){
                    add(here[i][pos]+1,bc);
                    break;
                }
                else{
                    add(here[i][pos]+1,here[i][pos+1]-1);
                    pos++;
                }
            }
        }

        for(auto [l1,r1,u] : prev_segs){
            for(auto [l2,r2,v] : curr_segs){
                if(max(l1,l2) <= min(r1,r2)){
                    edges.pb({u,v});
                }
            }
        }

        prev_segs = curr_segs;
    }

    ptr--;

    // debug(ptr);
    // debug(edges);

    DSU dsu(ptr+5);
    for(auto [u,v] : edges){
        dsu.merge(u,v);
    }

    int ans = 0;

    rep1(i,ptr){
        if(dsu.find(i) == i){
            ans++;
        }
    }

    return ans;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9604 KB Output is correct
3 Incorrect 1205 ms 13528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 12 ms 12320 KB Output is correct
3 Correct 13 ms 14980 KB Output is correct
4 Correct 13 ms 13388 KB Output is correct
5 Correct 12 ms 13000 KB Output is correct
6 Correct 16 ms 13196 KB Output is correct
7 Correct 21 ms 13556 KB Output is correct
8 Correct 8 ms 10480 KB Output is correct
9 Correct 8 ms 10452 KB Output is correct
10 Correct 7 ms 10088 KB Output is correct
11 Correct 8 ms 10556 KB Output is correct
12 Correct 7 ms 10472 KB Output is correct
13 Correct 10 ms 13296 KB Output is correct
14 Correct 9 ms 11732 KB Output is correct
15 Correct 9 ms 11856 KB Output is correct
16 Correct 15 ms 12872 KB Output is correct
17 Correct 12 ms 12168 KB Output is correct
18 Correct 12 ms 12492 KB Output is correct
19 Correct 13 ms 13896 KB Output is correct
20 Correct 14 ms 13132 KB Output is correct
21 Correct 28 ms 10644 KB Output is correct
22 Correct 43 ms 10836 KB Output is correct
23 Correct 14 ms 12128 KB Output is correct
24 Correct 19 ms 12980 KB Output is correct
25 Correct 17 ms 14184 KB Output is correct
26 Correct 23 ms 18800 KB Output is correct
27 Correct 21 ms 16216 KB Output is correct
28 Correct 21 ms 16384 KB Output is correct
29 Correct 19 ms 14416 KB Output is correct
30 Correct 20 ms 14440 KB Output is correct
31 Correct 25 ms 15356 KB Output is correct
32 Correct 18 ms 15584 KB Output is correct
33 Correct 18 ms 15524 KB Output is correct

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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