oj.uz

Submission #997638

# Submission time Handle Problem Language Result Execution time Memory
997638 2024-06-12T15:24:16 Z underwaterkillerwhale Stranded Far From Home (BOI22_island) C++17
100 / 100
 658 ms 136744 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], tot[N];
    vector<int> vec[N];
    set<pair<int,int>> Sadj[N];///greater val

    struct Data {
        int labu, labv, szu, szv, 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];
        tot[u] = min(tot[u], INF);
        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 24668 KB Output is correct
2 Correct 4 ms 24668 KB Output is correct
3 Correct 4 ms 24668 KB Output is correct
4 Correct 5 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 5 ms 25176 KB Output is correct
8 Correct 5 ms 25176 KB Output is correct
9 Correct 5 ms 25180 KB Output is correct
10 Correct 8 ms 25436 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 7 ms 25436 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 8 ms 25384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 4 ms 24668 KB Output is correct
3 Correct 196 ms 76576 KB Output is correct
4 Correct 179 ms 79688 KB Output is correct
5 Correct 484 ms 100860 KB Output is correct
6 Correct 530 ms 105984 KB Output is correct
7 Correct 505 ms 104796 KB Output is correct
8 Correct 311 ms 78280 KB Output is correct
9 Correct 468 ms 136744 KB Output is correct
10 Correct 211 ms 62924 KB Output is correct
11 Correct 229 ms 69780 KB Output is correct
12 Correct 367 ms 85196 KB Output is correct
13 Correct 167 ms 78232 KB Output is correct
14 Correct 173 ms 79452 KB Output is correct
15 Correct 163 ms 71456 KB Output is correct
16 Correct 135 ms 70856 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24668 KB Output is correct
2 Correct 634 ms 120992 KB Output is correct
3 Correct 654 ms 120912 KB Output is correct
4 Correct 177 ms 78280 KB Output is correct
5 Correct 178 ms 81672 KB Output is correct
6 Correct 634 ms 120044 KB Output is correct
7 Correct 175 ms 71684 KB Output is correct
8 Correct 171 ms 71364 KB Output is correct
9 Correct 135 ms 70856 KB Output is correct
10 Correct 177 ms 77364 KB Output is correct
11 Correct 297 ms 87244 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 517 ms 94312 KB Output is correct
3 Correct 518 ms 99012 KB Output is correct
4 Correct 591 ms 106536 KB Output is correct
5 Correct 528 ms 107384 KB Output is correct
6 Correct 436 ms 95940 KB Output is correct
7 Correct 283 ms 79172 KB Output is correct
8 Correct 140 ms 75040 KB Output is correct
9 Correct 324 ms 73672 KB Output is correct
10 Correct 542 ms 114636 KB Output is correct
11 Correct 279 ms 85264 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 4 ms 24668 KB Output is correct
3 Correct 4 ms 24668 KB Output is correct
4 Correct 5 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 5 ms 25176 KB Output is correct
8 Correct 5 ms 25176 KB Output is correct
9 Correct 5 ms 25180 KB Output is correct
10 Correct 8 ms 25436 KB Output is correct
11 Correct 7 ms 25436 KB Output is correct
12 Correct 7 ms 25436 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 8 ms 25384 KB Output is correct
15 Correct 4 ms 24668 KB Output is correct
16 Correct 4 ms 24668 KB Output is correct
17 Correct 196 ms 76576 KB Output is correct
18 Correct 179 ms 79688 KB Output is correct
19 Correct 484 ms 100860 KB Output is correct
20 Correct 530 ms 105984 KB Output is correct
21 Correct 505 ms 104796 KB Output is correct
22 Correct 311 ms 78280 KB Output is correct
23 Correct 468 ms 136744 KB Output is correct
24 Correct 211 ms 62924 KB Output is correct
25 Correct 229 ms 69780 KB Output is correct
26 Correct 367 ms 85196 KB Output is correct
27 Correct 167 ms 78232 KB Output is correct
28 Correct 173 ms 79452 KB Output is correct
29 Correct 163 ms 71456 KB Output is correct
30 Correct 135 ms 70856 KB Output is correct
31 Correct 5 ms 24668 KB Output is correct
32 Correct 634 ms 120992 KB Output is correct
33 Correct 654 ms 120912 KB Output is correct
34 Correct 177 ms 78280 KB Output is correct
35 Correct 178 ms 81672 KB Output is correct
36 Correct 634 ms 120044 KB Output is correct
37 Correct 175 ms 71684 KB Output is correct
38 Correct 171 ms 71364 KB Output is correct
39 Correct 135 ms 70856 KB Output is correct
40 Correct 177 ms 77364 KB Output is correct
41 Correct 297 ms 87244 KB Output is correct
42 Correct 4 ms 24668 KB Output is correct
43 Correct 517 ms 94312 KB Output is correct
44 Correct 518 ms 99012 KB Output is correct
45 Correct 591 ms 106536 KB Output is correct
46 Correct 528 ms 107384 KB Output is correct
47 Correct 436 ms 95940 KB Output is correct
48 Correct 283 ms 79172 KB Output is correct
49 Correct 140 ms 75040 KB Output is correct
50 Correct 324 ms 73672 KB Output is correct
51 Correct 542 ms 114636 KB Output is correct
52 Correct 279 ms 85264 KB Output is correct
53 Correct 4 ms 24668 KB Output is correct
54 Correct 4 ms 24668 KB Output is correct
55 Correct 4 ms 24748 KB Output is correct
56 Correct 6 ms 25132 KB Output is correct
57 Correct 6 ms 25176 KB Output is correct
58 Correct 6 ms 25180 KB Output is correct
59 Correct 6 ms 25176 KB Output is correct
60 Correct 5 ms 25232 KB Output is correct
61 Correct 4 ms 25180 KB Output is correct
62 Correct 7 ms 25436 KB Output is correct
63 Correct 8 ms 25432 KB Output is correct
64 Correct 9 ms 25692 KB Output is correct
65 Correct 5 ms 25180 KB Output is correct
66 Correct 6 ms 25436 KB Output is correct
67 Correct 184 ms 76608 KB Output is correct
68 Correct 188 ms 79564 KB Output is correct
69 Correct 476 ms 101116 KB Output is correct
70 Correct 515 ms 105984 KB Output is correct
71 Correct 531 ms 104796 KB Output is correct
72 Correct 307 ms 78284 KB Output is correct
73 Correct 450 ms 136744 KB Output is correct
74 Correct 212 ms 62848 KB Output is correct
75 Correct 229 ms 69696 KB Output is correct
76 Correct 383 ms 85092 KB Output is correct
77 Correct 165 ms 78296 KB Output is correct
78 Correct 165 ms 79560 KB Output is correct
79 Correct 157 ms 71320 KB Output is correct
80 Correct 125 ms 70856 KB Output is correct
81 Correct 645 ms 121036 KB Output is correct
82 Correct 658 ms 120772 KB Output is correct
83 Correct 178 ms 78276 KB Output is correct
84 Correct 176 ms 81748 KB Output is correct
85 Correct 599 ms 119832 KB Output is correct
86 Correct 178 ms 71368 KB Output is correct
87 Correct 170 ms 71360 KB Output is correct
88 Correct 183 ms 77256 KB Output is correct
89 Correct 302 ms 87240 KB Output is correct
90 Correct 495 ms 94328 KB Output is correct
91 Correct 531 ms 99016 KB Output is correct
92 Correct 592 ms 106320 KB Output is correct
93 Correct 517 ms 107200 KB Output is correct
94 Correct 419 ms 95944 KB Output is correct
95 Correct 275 ms 79164 KB Output is correct
96 Correct 143 ms 74952 KB Output is correct
97 Correct 344 ms 73708 KB Output is correct
98 Correct 562 ms 114888 KB Output is correct
99 Correct 279 ms 85192 KB Output is correct
100 Correct 123 ms 50768 KB Output is correct
101 Correct 555 ms 102652 KB Output is correct
102 Correct 366 ms 88344 KB Output is correct
103 Correct 376 ms 79528 KB Output is correct
104 Correct 437 ms 89544 KB Output is correct