oj.uz

Submission #997636

# Submission time Handle Problem Language Result Execution time Memory
997636 2024-06-12T15:21:30 Z underwaterkillerwhale Stranded Far From Home (BOI22_island) C++17
100 / 100
 690 ms 141612 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;

int n, m;
vector<int> ke[N];

int a[N];
pair<int,int> b[N];

bool Ans[N];
int larger[N];


struct Disjoin_set {
    int lab[N], sz[N];
    ll tot[N];
    vector<int> vec[N];
    set<pair<int,int>> Sadj[N];///greater val

    struct Data {
        int labu, labv, szu, szv;
        ll totu, totv;
    };

    stack<Data> op;

    void init (int n) {
        rep (i, 1, n) {
            lab[i] = i, sz[i] = 1, tot[i] = a[i];
            vec[i] = {i};
            iter (&id, ke[i]) {
                Sadj[i].insert(mp(a[id], id));
            }
        }
    }

    int Find (int u) {
        return u == lab[u] ? u : Find(lab[u]);
    }

    void Join (int u, int v) { /// u wanna combine, not v
        u = Find(u);
        v = Find(v);
        op.push({u, v, sz[u], sz[v], tot[u], tot[v]});
        if (u == v) return;
        if (sz[u] < sz[v]) swap(u, v);
        lab[v] = u;
        sz[u] += sz[v];
        iter (&id, vec[v]) {
            iter (&idto, ke[id]) {
                Sadj[u].insert(mp(a[idto], idto));
            }
            vec[u].push_back(id);
        }
        tot[u] += tot[v];
        vector<int> ().swap(vec[v]);
    }

    void roll_back() {
        Data cur = op.top();
        op.pop();
        int u = cur.labu, v = cur.labv;
        lab[u] = cur.labu, lab[v] = cur.labv;
        sz[u] = cur.szu, sz[v] = cur.szv;
        tot[u] = cur.totu, tot[v] = cur.totv;
    }

    int Find_Larger (int u) {
        int idx = u;
        u = Find(u);
        auto it = Sadj[u].lower_bound(mp(a[idx] + 1, -INF));
        if (it == Sadj[u].end()) return -1;
        else return it->se;
    }
}DSU;

void solution () {
    cin >> n >> m;
    rep (i, 1, n) {
        cin >> a[i];
        b[i].fs = a[i];
        b[i].se = i;
    }
    rep (i, 1, m) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    DSU.init(n);
    sort (b + 1, b + 1 + n);
    rep (i, 1, n) {
        static vector<int> vec; vec.clear();
        while (b[i].fs == b[i + 1].fs) vec.push_back(b[i++].se);
        vec.push_back(b[i].se);
        iter (&idx, vec) {
            iter (&to, ke[idx]) {
                if (a[idx] >= a[to]) {
                    DSU.Join (idx, to);
                }
            }
        }
        iter (&idx, vec) {
            larger[idx] = DSU.Find_Larger(idx);
        }
    }
    reb (i, n, 1) {
        static vector<int> vec; vec.clear();
        while (b[i].fs == b[i - 1].fs) vec.push_back(b[i--].se);
        vec.push_back(b[i].se);
        iter (&id, vec) {
            if (larger[id] == -1 || (DSU.tot[DSU.Find(id)] >= a[larger[id]] && Ans[larger[id]] == 1)) {
                Ans[id] = 1;
            }
            else Ans[id] = 0;
        }
        iter (&id, vec) iter (&to, ke[id]) {
            if (a[id] >= a[to]) {
                DSU.roll_back();
            }
        }
    }
    rep (i ,1, n) cout << Ans[i];
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
5 10
1 2
3 1
4 2
5 3
1 4
2 3
3 5
4 5
3 4
1 4

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25436 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 3 ms 25436 KB Output is correct
4 Correct 6 ms 26056 KB Output is correct
5 Correct 9 ms 26204 KB Output is correct
6 Correct 5 ms 26204 KB Output is correct
7 Correct 5 ms 26000 KB Output is correct
8 Correct 5 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 6 ms 26204 KB Output is correct
11 Correct 6 ms 26204 KB Output is correct
12 Correct 7 ms 26204 KB Output is correct
13 Correct 5 ms 25988 KB Output is correct
14 Correct 6 ms 26204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25436 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 199 ms 81748 KB Output is correct
4 Correct 196 ms 85452 KB Output is correct
5 Correct 455 ms 105728 KB Output is correct
6 Correct 544 ms 111172 KB Output is correct
7 Correct 507 ms 109876 KB Output is correct
8 Correct 308 ms 85196 KB Output is correct
9 Correct 500 ms 141612 KB Output is correct
10 Correct 222 ms 67268 KB Output is correct
11 Correct 286 ms 75844 KB Output is correct
12 Correct 397 ms 91284 KB Output is correct
13 Correct 184 ms 84420 KB Output is correct
14 Correct 201 ms 85676 KB Output is correct
15 Correct 163 ms 76384 KB Output is correct
16 Correct 134 ms 75460 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25432 KB Output is correct
2 Correct 669 ms 126112 KB Output is correct
3 Correct 631 ms 123212 KB Output is correct
4 Correct 187 ms 82628 KB Output is correct
5 Correct 204 ms 85924 KB Output is correct
6 Correct 662 ms 122388 KB Output is correct
7 Correct 189 ms 73880 KB Output is correct
8 Correct 255 ms 73928 KB Output is correct
9 Correct 131 ms 73412 KB Output is correct
10 Correct 184 ms 79936 KB Output is correct
11 Correct 348 ms 90200 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25432 KB Output is correct
2 Correct 529 ms 97036 KB Output is correct
3 Correct 517 ms 101716 KB Output is correct
4 Correct 603 ms 109148 KB Output is correct
5 Correct 519 ms 111424 KB Output is correct
6 Correct 429 ms 100064 KB Output is correct
7 Correct 274 ms 83320 KB Output is correct
8 Correct 146 ms 78532 KB Output is correct
9 Correct 340 ms 76508 KB Output is correct
10 Correct 578 ms 118876 KB Output is correct
11 Correct 268 ms 88152 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25436 KB Output is correct
2 Correct 4 ms 25436 KB Output is correct
3 Correct 3 ms 25436 KB Output is correct
4 Correct 6 ms 26056 KB Output is correct
5 Correct 9 ms 26204 KB Output is correct
6 Correct 5 ms 26204 KB Output is correct
7 Correct 5 ms 26000 KB Output is correct
8 Correct 5 ms 25948 KB Output is correct
9 Correct 5 ms 25948 KB Output is correct
10 Correct 6 ms 26204 KB Output is correct
11 Correct 6 ms 26204 KB Output is correct
12 Correct 7 ms 26204 KB Output is correct
13 Correct 5 ms 25988 KB Output is correct
14 Correct 6 ms 26204 KB Output is correct
15 Correct 3 ms 25436 KB Output is correct
16 Correct 4 ms 25436 KB Output is correct
17 Correct 199 ms 81748 KB Output is correct
18 Correct 196 ms 85452 KB Output is correct
19 Correct 455 ms 105728 KB Output is correct
20 Correct 544 ms 111172 KB Output is correct
21 Correct 507 ms 109876 KB Output is correct
22 Correct 308 ms 85196 KB Output is correct
23 Correct 500 ms 141612 KB Output is correct
24 Correct 222 ms 67268 KB Output is correct
25 Correct 286 ms 75844 KB Output is correct
26 Correct 397 ms 91284 KB Output is correct
27 Correct 184 ms 84420 KB Output is correct
28 Correct 201 ms 85676 KB Output is correct
29 Correct 163 ms 76384 KB Output is correct
30 Correct 134 ms 75460 KB Output is correct
31 Correct 4 ms 25432 KB Output is correct
32 Correct 669 ms 126112 KB Output is correct
33 Correct 631 ms 123212 KB Output is correct
34 Correct 187 ms 82628 KB Output is correct
35 Correct 204 ms 85924 KB Output is correct
36 Correct 662 ms 122388 KB Output is correct
37 Correct 189 ms 73880 KB Output is correct
38 Correct 255 ms 73928 KB Output is correct
39 Correct 131 ms 73412 KB Output is correct
40 Correct 184 ms 79936 KB Output is correct
41 Correct 348 ms 90200 KB Output is correct
42 Correct 3 ms 25432 KB Output is correct
43 Correct 529 ms 97036 KB Output is correct
44 Correct 517 ms 101716 KB Output is correct
45 Correct 603 ms 109148 KB Output is correct
46 Correct 519 ms 111424 KB Output is correct
47 Correct 429 ms 100064 KB Output is correct
48 Correct 274 ms 83320 KB Output is correct
49 Correct 146 ms 78532 KB Output is correct
50 Correct 340 ms 76508 KB Output is correct
51 Correct 578 ms 118876 KB Output is correct
52 Correct 268 ms 88152 KB Output is correct
53 Correct 3 ms 25432 KB Output is correct
54 Correct 4 ms 25436 KB Output is correct
55 Correct 3 ms 25504 KB Output is correct
56 Correct 6 ms 25948 KB Output is correct
57 Correct 8 ms 26008 KB Output is correct
58 Correct 8 ms 26200 KB Output is correct
59 Correct 5 ms 25944 KB Output is correct
60 Correct 5 ms 26008 KB Output is correct
61 Correct 5 ms 25948 KB Output is correct
62 Correct 6 ms 26256 KB Output is correct
63 Correct 6 ms 26200 KB Output is correct
64 Correct 6 ms 26200 KB Output is correct
65 Correct 5 ms 25948 KB Output is correct
66 Correct 6 ms 26204 KB Output is correct
67 Correct 213 ms 79048 KB Output is correct
68 Correct 182 ms 83916 KB Output is correct
69 Correct 490 ms 103452 KB Output is correct
70 Correct 582 ms 108444 KB Output is correct
71 Correct 491 ms 107100 KB Output is correct
72 Correct 306 ms 82496 KB Output is correct
73 Correct 477 ms 139248 KB Output is correct
74 Correct 220 ms 65388 KB Output is correct
75 Correct 237 ms 73792 KB Output is correct
76 Correct 376 ms 89284 KB Output is correct
77 Correct 171 ms 82480 KB Output is correct
78 Correct 166 ms 83760 KB Output is correct
79 Correct 179 ms 73928 KB Output is correct
80 Correct 126 ms 73416 KB Output is correct
81 Correct 690 ms 123548 KB Output is correct
82 Correct 622 ms 123324 KB Output is correct
83 Correct 189 ms 82628 KB Output is correct
84 Correct 214 ms 86060 KB Output is correct
85 Correct 625 ms 122524 KB Output is correct
86 Correct 185 ms 73924 KB Output is correct
87 Correct 195 ms 73920 KB Output is correct
88 Correct 175 ms 79812 KB Output is correct
89 Correct 288 ms 90196 KB Output is correct
90 Correct 510 ms 97116 KB Output is correct
91 Correct 577 ms 101712 KB Output is correct
92 Correct 582 ms 109156 KB Output is correct
93 Correct 563 ms 111548 KB Output is correct
94 Correct 416 ms 100040 KB Output is correct
95 Correct 277 ms 83268 KB Output is correct
96 Correct 150 ms 78532 KB Output is correct
97 Correct 343 ms 76512 KB Output is correct
98 Correct 595 ms 118824 KB Output is correct
99 Correct 271 ms 88152 KB Output is correct
100 Correct 119 ms 53328 KB Output is correct
101 Correct 581 ms 105080 KB Output is correct
102 Correct 365 ms 92616 KB Output is correct
103 Correct 429 ms 81928 KB Output is correct
104 Correct 474 ms 92104 KB Output is correct