oj.uz

Submission #749277

# Submission time Handle Problem Language Result Execution time Memory
749277 2023-05-27T16:17:05 Z GrindMachine Stranded Far From Home (BOI22_island) C++17
100 / 100
 628 ms 77540 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

/*

refs:
edi
https://github.com/koosaga/olympiad/blob/master/Baltic/baltic22_island.cpp

*/

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

set<pll> st;

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

    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);
        val = vector<ll>(n + 1);
        here = vector<vector<int>>(n+1);
        rep(i, n + 1) create(i);
    }

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

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

        if(st.count({val[u], u})){
            st.erase({val[u], u});
        }

        if(st.count({val[v], v})){
            st.erase({val[v], v});
        }

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

        st.insert({val[u], u});

        if(sz(here[u]) < sz(here[v])){
            swap(here[u], here[v]);
        }

        trav(x,here[v]){
            here[u].pb(x);
        }

        here[v].clear();
    }
};

vector<ll> adj[N];

void solve(int test_case)
{
    ll n,m; cin >> n >> m;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];
    rep1(i,m){
        ll u,v; cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }

    map<ll,vector<ll>> mp;
    rep1(i,n) mp[a[i]].pb(i);

    vector<pair<ll,vector<ll>>> b;
    trav(p,mp) b.pb(p);

    DSU dsu(n+5);
    vector<ll> ans(n+5,1);

    rep(i,sz(b)-1){
        trav(u,b[i].ss){
            dsu.val[u] = a[u];
            st.insert({a[u], u});
        }

        trav(u,b[i].ss){
            trav(v,adj[u]){
                if(a[v] <= a[u]){
                    dsu.merge(u,v);
                }
            }
        }

        ll nxt = b[i+1].ff;

        while(!st.empty()){
            auto [mn, root] = *st.begin();
            if(mn < nxt){
                st.erase(st.begin());
                trav(u,dsu.here[root]){
                    ans[u] = 0;
                }
            }
            else{
                break;
            }
        }
    }

    rep1(i,n) cout << ans[i];
    cout << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

island.cpp: In function 'void solve(int)':
island.cpp:30:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i, n) for(int i = 0; i < n; ++i)
......
  159 |     rep(i,sz(b)-1){
      |         ~~~~~~~~~                   
island.cpp:159:5: note: in expansion of macro 'rep'
  159 |     rep(i,sz(b)-1){
      |     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 5 ms 5540 KB Output is correct
5 Correct 5 ms 5588 KB Output is correct
6 Correct 4 ms 5160 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 6 ms 5600 KB Output is correct
11 Correct 6 ms 5672 KB Output is correct
12 Correct 5 ms 5576 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 5 ms 5332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 264 ms 71000 KB Output is correct
4 Correct 298 ms 47788 KB Output is correct
5 Correct 411 ms 74500 KB Output is correct
6 Correct 445 ms 69032 KB Output is correct
7 Correct 412 ms 76716 KB Output is correct
8 Correct 424 ms 51776 KB Output is correct
9 Correct 316 ms 72852 KB Output is correct
10 Correct 168 ms 61452 KB Output is correct
11 Correct 100 ms 37580 KB Output is correct
12 Correct 436 ms 47796 KB Output is correct
13 Correct 325 ms 48104 KB Output is correct
14 Correct 285 ms 46880 KB Output is correct
15 Correct 241 ms 70068 KB Output is correct
16 Correct 185 ms 68728 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 530 ms 76396 KB Output is correct
3 Correct 496 ms 69848 KB Output is correct
4 Correct 128 ms 37008 KB Output is correct
5 Correct 339 ms 48044 KB Output is correct
6 Correct 528 ms 77488 KB Output is correct
7 Correct 250 ms 70212 KB Output is correct
8 Correct 232 ms 70140 KB Output is correct
9 Correct 192 ms 68844 KB Output is correct
10 Correct 355 ms 58252 KB Output is correct
11 Correct 317 ms 42356 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 397 ms 41980 KB Output is correct
3 Correct 400 ms 41460 KB Output is correct
4 Correct 435 ms 41948 KB Output is correct
5 Correct 142 ms 37916 KB Output is correct
6 Correct 141 ms 36540 KB Output is correct
7 Correct 363 ms 51868 KB Output is correct
8 Correct 271 ms 44196 KB Output is correct
9 Correct 171 ms 26144 KB Output is correct
10 Correct 611 ms 52472 KB Output is correct
11 Correct 310 ms 41156 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 5 ms 5540 KB Output is correct
5 Correct 5 ms 5588 KB Output is correct
6 Correct 4 ms 5160 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 5 ms 5332 KB Output is correct
10 Correct 6 ms 5600 KB Output is correct
11 Correct 6 ms 5672 KB Output is correct
12 Correct 5 ms 5576 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 5 ms 5332 KB Output is correct
15 Correct 3 ms 5016 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Correct 264 ms 71000 KB Output is correct
18 Correct 298 ms 47788 KB Output is correct
19 Correct 411 ms 74500 KB Output is correct
20 Correct 445 ms 69032 KB Output is correct
21 Correct 412 ms 76716 KB Output is correct
22 Correct 424 ms 51776 KB Output is correct
23 Correct 316 ms 72852 KB Output is correct
24 Correct 168 ms 61452 KB Output is correct
25 Correct 100 ms 37580 KB Output is correct
26 Correct 436 ms 47796 KB Output is correct
27 Correct 325 ms 48104 KB Output is correct
28 Correct 285 ms 46880 KB Output is correct
29 Correct 241 ms 70068 KB Output is correct
30 Correct 185 ms 68728 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Correct 530 ms 76396 KB Output is correct
33 Correct 496 ms 69848 KB Output is correct
34 Correct 128 ms 37008 KB Output is correct
35 Correct 339 ms 48044 KB Output is correct
36 Correct 528 ms 77488 KB Output is correct
37 Correct 250 ms 70212 KB Output is correct
38 Correct 232 ms 70140 KB Output is correct
39 Correct 192 ms 68844 KB Output is correct
40 Correct 355 ms 58252 KB Output is correct
41 Correct 317 ms 42356 KB Output is correct
42 Correct 3 ms 4940 KB Output is correct
43 Correct 397 ms 41980 KB Output is correct
44 Correct 400 ms 41460 KB Output is correct
45 Correct 435 ms 41948 KB Output is correct
46 Correct 142 ms 37916 KB Output is correct
47 Correct 141 ms 36540 KB Output is correct
48 Correct 363 ms 51868 KB Output is correct
49 Correct 271 ms 44196 KB Output is correct
50 Correct 171 ms 26144 KB Output is correct
51 Correct 611 ms 52472 KB Output is correct
52 Correct 310 ms 41156 KB Output is correct
53 Correct 2 ms 4948 KB Output is correct
54 Correct 3 ms 4948 KB Output is correct
55 Correct 4 ms 5024 KB Output is correct
56 Correct 5 ms 5540 KB Output is correct
57 Correct 6 ms 5584 KB Output is correct
58 Correct 4 ms 5204 KB Output is correct
59 Correct 5 ms 5416 KB Output is correct
60 Correct 4 ms 5460 KB Output is correct
61 Correct 4 ms 5332 KB Output is correct
62 Correct 5 ms 5588 KB Output is correct
63 Correct 6 ms 5588 KB Output is correct
64 Correct 6 ms 5588 KB Output is correct
65 Correct 4 ms 5392 KB Output is correct
66 Correct 6 ms 5332 KB Output is correct
67 Correct 264 ms 70916 KB Output is correct
68 Correct 383 ms 47748 KB Output is correct
69 Correct 433 ms 74480 KB Output is correct
70 Correct 382 ms 68996 KB Output is correct
71 Correct 453 ms 76716 KB Output is correct
72 Correct 450 ms 51756 KB Output is correct
73 Correct 292 ms 72832 KB Output is correct
74 Correct 176 ms 61440 KB Output is correct
75 Correct 101 ms 37528 KB Output is correct
76 Correct 495 ms 47820 KB Output is correct
77 Correct 363 ms 48016 KB Output is correct
78 Correct 306 ms 46908 KB Output is correct
79 Correct 255 ms 70188 KB Output is correct
80 Correct 183 ms 68760 KB Output is correct
81 Correct 525 ms 76460 KB Output is correct
82 Correct 628 ms 69968 KB Output is correct
83 Correct 119 ms 37052 KB Output is correct
84 Correct 324 ms 48020 KB Output is correct
85 Correct 577 ms 77540 KB Output is correct
86 Correct 233 ms 70152 KB Output is correct
87 Correct 260 ms 70192 KB Output is correct
88 Correct 333 ms 58388 KB Output is correct
89 Correct 306 ms 42452 KB Output is correct
90 Correct 398 ms 42036 KB Output is correct
91 Correct 374 ms 41376 KB Output is correct
92 Correct 403 ms 41964 KB Output is correct
93 Correct 134 ms 37792 KB Output is correct
94 Correct 136 ms 36420 KB Output is correct
95 Correct 446 ms 51880 KB Output is correct
96 Correct 283 ms 44292 KB Output is correct
97 Correct 172 ms 26308 KB Output is correct
98 Correct 597 ms 52464 KB Output is correct
99 Correct 300 ms 41268 KB Output is correct
100 Correct 46 ms 11852 KB Output is correct
101 Correct 583 ms 67640 KB Output is correct
102 Correct 123 ms 31964 KB Output is correct
103 Correct 433 ms 55924 KB Output is correct
104 Correct 523 ms 72040 KB Output is correct