Submission #997630

# Submission time Handle Problem Language Result Execution time Memory
997630 2024-06-12T15:14:27 Z underwaterkillerwhale Stranded Far From Home (BOI22_island) C++17
100 / 100
785 ms 146728 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];

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

pair<int,int> b[N];

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

    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 : lab[u] = Find(lab[u]);
    }

    void Join (int u, int v) { /// u wanna combine, not v
        u = Find(u);
        v = Find(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]);
    }
    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;

struct Disjoin_set2 {
    int lab[N], sz[N];
    ll tot[N];
    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];
        }
    }

    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({lab[u], lab[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];
        tot[u] += tot[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;
    }

}DSU2;

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);
    DSU2.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);
                    DSU2.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) {
//            cout << id<<": "<<DSU2.tot[DSU2.Find(id)]<<"\n";
            if (larger[id] == -1 || (DSU2.tot[DSU2.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]) {
//                cout << id
                DSU2.roll_back();
            }
        }
    }
//    rep (i, 1, n) cout << i <<" "<<larger[i] <<"\n";
    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

*/
# Verdict Execution time Memory Grader output
1 Correct 4 ms 28504 KB Output is correct
2 Correct 4 ms 28504 KB Output is correct
3 Correct 4 ms 28504 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29016 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 7 ms 29380 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 7 ms 29532 KB Output is correct
13 Correct 5 ms 29276 KB Output is correct
14 Correct 7 ms 29272 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 28508 KB Output is correct
2 Correct 4 ms 28608 KB Output is correct
3 Correct 198 ms 82376 KB Output is correct
4 Correct 176 ms 86784 KB Output is correct
5 Correct 515 ms 106476 KB Output is correct
6 Correct 509 ms 111516 KB Output is correct
7 Correct 500 ms 110424 KB Output is correct
8 Correct 316 ms 85704 KB Output is correct
9 Correct 536 ms 142284 KB Output is correct
10 Correct 211 ms 68292 KB Output is correct
11 Correct 246 ms 77124 KB Output is correct
12 Correct 366 ms 92364 KB Output is correct
13 Correct 194 ms 85700 KB Output is correct
14 Correct 179 ms 86984 KB Output is correct
15 Correct 178 ms 77088 KB Output is correct
16 Correct 228 ms 76488 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 28504 KB Output is correct
2 Correct 785 ms 126624 KB Output is correct
3 Correct 785 ms 130912 KB Output is correct
4 Correct 248 ms 90080 KB Output is correct
5 Correct 228 ms 92016 KB Output is correct
6 Correct 759 ms 130064 KB Output is correct
7 Correct 255 ms 81600 KB Output is correct
8 Correct 199 ms 81348 KB Output is correct
9 Correct 146 ms 80308 KB Output is correct
10 Correct 216 ms 86720 KB Output is correct
11 Correct 319 ms 96340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 28504 KB Output is correct
2 Correct 589 ms 102664 KB Output is correct
3 Correct 593 ms 109164 KB Output is correct
4 Correct 671 ms 116536 KB Output is correct
5 Correct 590 ms 119052 KB Output is correct
6 Correct 466 ms 107576 KB Output is correct
7 Correct 309 ms 90948 KB Output is correct
8 Correct 160 ms 84936 KB Output is correct
9 Correct 351 ms 82160 KB Output is correct
10 Correct 629 ms 124900 KB Output is correct
11 Correct 352 ms 94296 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 28504 KB Output is correct
2 Correct 4 ms 28504 KB Output is correct
3 Correct 4 ms 28504 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29016 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 7 ms 29380 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 7 ms 29532 KB Output is correct
13 Correct 5 ms 29276 KB Output is correct
14 Correct 7 ms 29272 KB Output is correct
15 Correct 4 ms 28508 KB Output is correct
16 Correct 4 ms 28608 KB Output is correct
17 Correct 198 ms 82376 KB Output is correct
18 Correct 176 ms 86784 KB Output is correct
19 Correct 515 ms 106476 KB Output is correct
20 Correct 509 ms 111516 KB Output is correct
21 Correct 500 ms 110424 KB Output is correct
22 Correct 316 ms 85704 KB Output is correct
23 Correct 536 ms 142284 KB Output is correct
24 Correct 211 ms 68292 KB Output is correct
25 Correct 246 ms 77124 KB Output is correct
26 Correct 366 ms 92364 KB Output is correct
27 Correct 194 ms 85700 KB Output is correct
28 Correct 179 ms 86984 KB Output is correct
29 Correct 178 ms 77088 KB Output is correct
30 Correct 228 ms 76488 KB Output is correct
31 Correct 4 ms 28504 KB Output is correct
32 Correct 785 ms 126624 KB Output is correct
33 Correct 785 ms 130912 KB Output is correct
34 Correct 248 ms 90080 KB Output is correct
35 Correct 228 ms 92016 KB Output is correct
36 Correct 759 ms 130064 KB Output is correct
37 Correct 255 ms 81600 KB Output is correct
38 Correct 199 ms 81348 KB Output is correct
39 Correct 146 ms 80308 KB Output is correct
40 Correct 216 ms 86720 KB Output is correct
41 Correct 319 ms 96340 KB Output is correct
42 Correct 4 ms 28504 KB Output is correct
43 Correct 589 ms 102664 KB Output is correct
44 Correct 593 ms 109164 KB Output is correct
45 Correct 671 ms 116536 KB Output is correct
46 Correct 590 ms 119052 KB Output is correct
47 Correct 466 ms 107576 KB Output is correct
48 Correct 309 ms 90948 KB Output is correct
49 Correct 160 ms 84936 KB Output is correct
50 Correct 351 ms 82160 KB Output is correct
51 Correct 629 ms 124900 KB Output is correct
52 Correct 352 ms 94296 KB Output is correct
53 Correct 6 ms 28764 KB Output is correct
54 Correct 4 ms 28508 KB Output is correct
55 Correct 4 ms 28604 KB Output is correct
56 Correct 7 ms 29260 KB Output is correct
57 Correct 7 ms 29388 KB Output is correct
58 Correct 7 ms 29276 KB Output is correct
59 Correct 7 ms 29020 KB Output is correct
60 Correct 7 ms 29016 KB Output is correct
61 Correct 6 ms 29020 KB Output is correct
62 Correct 7 ms 29276 KB Output is correct
63 Correct 7 ms 29272 KB Output is correct
64 Correct 8 ms 29532 KB Output is correct
65 Correct 5 ms 29136 KB Output is correct
66 Correct 6 ms 29276 KB Output is correct
67 Correct 217 ms 86772 KB Output is correct
68 Correct 189 ms 89948 KB Output is correct
69 Correct 519 ms 110868 KB Output is correct
70 Correct 561 ms 116116 KB Output is correct
71 Correct 539 ms 114776 KB Output is correct
72 Correct 371 ms 90140 KB Output is correct
73 Correct 590 ms 146728 KB Output is correct
74 Correct 293 ms 71896 KB Output is correct
75 Correct 274 ms 80424 KB Output is correct
76 Correct 476 ms 95464 KB Output is correct
77 Correct 290 ms 88640 KB Output is correct
78 Correct 251 ms 90084 KB Output is correct
79 Correct 191 ms 81512 KB Output is correct
80 Correct 143 ms 80132 KB Output is correct
81 Correct 775 ms 130992 KB Output is correct
82 Correct 771 ms 130960 KB Output is correct
83 Correct 242 ms 90172 KB Output is correct
84 Correct 223 ms 92096 KB Output is correct
85 Correct 745 ms 130112 KB Output is correct
86 Correct 228 ms 81436 KB Output is correct
87 Correct 221 ms 81308 KB Output is correct
88 Correct 206 ms 86724 KB Output is correct
89 Correct 310 ms 96340 KB Output is correct
90 Correct 559 ms 104572 KB Output is correct
91 Correct 573 ms 109144 KB Output is correct
92 Correct 636 ms 116576 KB Output is correct
93 Correct 555 ms 118984 KB Output is correct
94 Correct 454 ms 107464 KB Output is correct
95 Correct 292 ms 90692 KB Output is correct
96 Correct 156 ms 84932 KB Output is correct
97 Correct 356 ms 82144 KB Output is correct
98 Correct 617 ms 124884 KB Output is correct
99 Correct 281 ms 94296 KB Output is correct
100 Correct 122 ms 58316 KB Output is correct
101 Correct 600 ms 112600 KB Output is correct
102 Correct 452 ms 99788 KB Output is correct
103 Correct 405 ms 89280 KB Output is correct
104 Correct 514 ms 99528 KB Output is correct