oj.uz

Submission #824167

# Submission time Handle Problem Language Result Execution time Memory
824167 2023-08-13T16:24:53 Z GrindMachine Land of the Rainbow Gold (APIO17_rainbow) C++17
24 / 100
 1290 ms 18760 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;
        int optr = ptr;

        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;
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:148:13: warning: unused variable 'optr' [-Wunused-variable]
  148 |         int optr = ptr;
      |             ^~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 4 ms 9684 KB Output is correct
2 Correct 4 ms 9696 KB Output is correct
3 Incorrect 1290 ms 10804 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 11 ms 12108 KB Output is correct
3 Correct 13 ms 14800 KB Output is correct
4 Correct 12 ms 13260 KB Output is correct
5 Correct 12 ms 12904 KB Output is correct
6 Correct 18 ms 13132 KB Output is correct
7 Correct 16 ms 13360 KB Output is correct
8 Correct 8 ms 10448 KB Output is correct
9 Correct 7 ms 10324 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 7 ms 10452 KB Output is correct
12 Correct 8 ms 10440 KB Output is correct
13 Correct 9 ms 13140 KB Output is correct
14 Correct 9 ms 11632 KB Output is correct
15 Correct 9 ms 11744 KB Output is correct
16 Correct 14 ms 12744 KB Output is correct
17 Correct 16 ms 12020 KB Output is correct
18 Correct 11 ms 12364 KB Output is correct
19 Correct 13 ms 13868 KB Output is correct
20 Correct 11 ms 13000 KB Output is correct
21 Correct 22 ms 10468 KB Output is correct
22 Correct 44 ms 10836 KB Output is correct
23 Correct 18 ms 12160 KB Output is correct
24 Correct 19 ms 12884 KB Output is correct
25 Correct 17 ms 13992 KB Output is correct
26 Correct 26 ms 18760 KB Output is correct
27 Correct 21 ms 16200 KB Output is correct
28 Correct 23 ms 16348 KB Output is correct
29 Correct 20 ms 14336 KB Output is correct
30 Correct 21 ms 14360 KB Output is correct
31 Correct 26 ms 15236 KB Output is correct
32 Correct 19 ms 15436 KB Output is correct
33 Correct 18 ms 15400 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -