oj.uz

Submission #1066761

# Submission time Handle Problem Language Result Execution time Memory
1066761 2024-08-20T06:35:20 Z mispertion Stranded Far From Home (BOI22_island) C++17
100 / 100
 345 ms 85240 KB 
#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize("Ofast")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 3e5 + 10;
const int M = 1e5 + 10;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = 1e16;
const int P = 2;

int mult(int a, int b){
    return a * 1LL * b % mod;
}

int sum(int a, int b){
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}

int binpow(int a, int n){
    if (n == 0)
        return 1;
    if (n % 2 == 1){
        return mult(binpow(a, n - 1), a);
    }
    else{
        auto b = binpow(a, n / 2);
        return mult(b, b);
    }
}

int n, m, s[N], zav[N], ans[N];
map<int, vector<int>> mp;
vector<int> g[N];

struct dsu{
    set<pii> nbr[N];
    int p[N], sz[N], sm[N];

    dsu(int n){
        for(int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
            sm[i] = s[i];
            for(auto u : g[i])
                if(s[u] > s[i])
                    nbr[i].insert({s[u], u});
        }
    }

    int getp(int v){
        if(p[v] == v)
            return v;
        return p[v] = getp(p[v]);
    }

    void uni(int a, int b){
        a = getp(a);
        b = getp(b);
        if(a == b)
            return;
        if(sz[a] > sz[b])   
            swap(a, b);
        p[a] = b;
        sz[b] += sz[a];
        sm[b] += sm[a];
        if(sz(nbr[b]) > sz(nbr[a])){
            while(sz(nbr[a]) > 0){
                nbr[b].insert(*nbr[a].begin());
                nbr[a].erase(nbr[a].begin());
            }
        }else{
            set<pii> tmp = nbr[b];
            nbr[b].swap(nbr[a]);
            for(auto e : tmp)
                nbr[b].insert(e);
        }
    }
};

void solve(){
    cin >> n >> m;
    vector<pii> por = {};
    for(int i = 1; i <= n; i++){
        ans[i] = -1;
        cin >> s[i];
        por.pb({s[i], i});
        mp[s[i]].pb(i);
    }
    sort(all(por));
    reverse(all(por));
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        g[v].pb(u);
        g[u].pb(v);
    }
    dsu ds = dsu(n);
    for(auto e : mp){
        int w = e.F;
        for(auto v : e.S){
            for(auto u : g[v]){
                if(s[u] <= s[v])
                    ds.uni(u, v);
            }
        }
        for(auto v : e.S){
            int nv = ds.getp(v);
            while(sz(ds.nbr[nv]) > 0 && ds.nbr[nv].begin()->F <= w)
                ds.nbr[nv].erase(ds.nbr[nv].begin());
            if(sz(ds.nbr[nv]) == 0){
                ans[v] = 1;
            }else{
                if(ds.nbr[nv].begin()->F <= ds.sm[nv]){
                    zav[v] = ds.nbr[nv].begin()->S;
                }else{
                    ans[v] = 0;
                }
            }
        }
    }
    for(auto e : por){
        if(ans[e.S] == -1){
            ans[e.S] = ans[zav[e.S]];
        }
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i];
    cout << '\n';
}

signed main(){
    mispertion;
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33884 KB Output is correct
2 Correct 15 ms 33956 KB Output is correct
3 Correct 13 ms 31836 KB Output is correct
4 Correct 14 ms 34488 KB Output is correct
5 Correct 14 ms 34396 KB Output is correct
6 Correct 13 ms 32092 KB Output is correct
7 Correct 15 ms 34352 KB Output is correct
8 Correct 16 ms 34396 KB Output is correct
9 Correct 13 ms 32180 KB Output is correct
10 Correct 14 ms 34320 KB Output is correct
11 Correct 15 ms 34396 KB Output is correct
12 Correct 14 ms 34396 KB Output is correct
13 Correct 13 ms 31928 KB Output is correct
14 Correct 14 ms 34136 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33880 KB Output is correct
2 Correct 13 ms 31832 KB Output is correct
3 Correct 175 ms 84372 KB Output is correct
4 Correct 93 ms 52452 KB Output is correct
5 Correct 193 ms 82616 KB Output is correct
6 Correct 182 ms 79028 KB Output is correct
7 Correct 201 ms 84404 KB Output is correct
8 Correct 106 ms 53560 KB Output is correct
9 Correct 157 ms 80564 KB Output is correct
10 Correct 167 ms 79028 KB Output is correct
11 Correct 105 ms 52452 KB Output is correct
12 Correct 109 ms 53308 KB Output is correct
13 Correct 93 ms 50332 KB Output is correct
14 Correct 94 ms 50452 KB Output is correct
15 Correct 161 ms 83148 KB Output is correct
16 Correct 128 ms 81952 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32024 KB Output is correct
2 Correct 317 ms 83240 KB Output is correct
3 Correct 308 ms 79288 KB Output is correct
4 Correct 123 ms 52028 KB Output is correct
5 Correct 100 ms 51004 KB Output is correct
6 Correct 325 ms 83660 KB Output is correct
7 Correct 165 ms 83380 KB Output is correct
8 Correct 174 ms 83312 KB Output is correct
9 Correct 129 ms 82100 KB Output is correct
10 Correct 176 ms 73828 KB Output is correct
11 Correct 186 ms 61876 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31788 KB Output is correct
2 Correct 228 ms 63636 KB Output is correct
3 Correct 223 ms 64552 KB Output is correct
4 Correct 230 ms 63696 KB Output is correct
5 Correct 136 ms 53816 KB Output is correct
6 Correct 115 ms 52284 KB Output is correct
7 Correct 94 ms 53636 KB Output is correct
8 Correct 101 ms 58168 KB Output is correct
9 Correct 145 ms 55444 KB Output is correct
10 Correct 112 ms 51536 KB Output is correct
11 Correct 157 ms 60920 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33884 KB Output is correct
2 Correct 15 ms 33956 KB Output is correct
3 Correct 13 ms 31836 KB Output is correct
4 Correct 14 ms 34488 KB Output is correct
5 Correct 14 ms 34396 KB Output is correct
6 Correct 13 ms 32092 KB Output is correct
7 Correct 15 ms 34352 KB Output is correct
8 Correct 16 ms 34396 KB Output is correct
9 Correct 13 ms 32180 KB Output is correct
10 Correct 14 ms 34320 KB Output is correct
11 Correct 15 ms 34396 KB Output is correct
12 Correct 14 ms 34396 KB Output is correct
13 Correct 13 ms 31928 KB Output is correct
14 Correct 14 ms 34136 KB Output is correct
15 Correct 13 ms 33880 KB Output is correct
16 Correct 13 ms 31832 KB Output is correct
17 Correct 175 ms 84372 KB Output is correct
18 Correct 93 ms 52452 KB Output is correct
19 Correct 193 ms 82616 KB Output is correct
20 Correct 182 ms 79028 KB Output is correct
21 Correct 201 ms 84404 KB Output is correct
22 Correct 106 ms 53560 KB Output is correct
23 Correct 157 ms 80564 KB Output is correct
24 Correct 167 ms 79028 KB Output is correct
25 Correct 105 ms 52452 KB Output is correct
26 Correct 109 ms 53308 KB Output is correct
27 Correct 93 ms 50332 KB Output is correct
28 Correct 94 ms 50452 KB Output is correct
29 Correct 161 ms 83148 KB Output is correct
30 Correct 128 ms 81952 KB Output is correct
31 Correct 13 ms 32024 KB Output is correct
32 Correct 317 ms 83240 KB Output is correct
33 Correct 308 ms 79288 KB Output is correct
34 Correct 123 ms 52028 KB Output is correct
35 Correct 100 ms 51004 KB Output is correct
36 Correct 325 ms 83660 KB Output is correct
37 Correct 165 ms 83380 KB Output is correct
38 Correct 174 ms 83312 KB Output is correct
39 Correct 129 ms 82100 KB Output is correct
40 Correct 176 ms 73828 KB Output is correct
41 Correct 186 ms 61876 KB Output is correct
42 Correct 14 ms 31788 KB Output is correct
43 Correct 228 ms 63636 KB Output is correct
44 Correct 223 ms 64552 KB Output is correct
45 Correct 230 ms 63696 KB Output is correct
46 Correct 136 ms 53816 KB Output is correct
47 Correct 115 ms 52284 KB Output is correct
48 Correct 94 ms 53636 KB Output is correct
49 Correct 101 ms 58168 KB Output is correct
50 Correct 145 ms 55444 KB Output is correct
51 Correct 112 ms 51536 KB Output is correct
52 Correct 157 ms 60920 KB Output is correct
53 Correct 12 ms 34136 KB Output is correct
54 Correct 12 ms 33880 KB Output is correct
55 Correct 12 ms 31864 KB Output is correct
56 Correct 14 ms 34392 KB Output is correct
57 Correct 14 ms 34392 KB Output is correct
58 Correct 14 ms 32088 KB Output is correct
59 Correct 16 ms 34336 KB Output is correct
60 Correct 13 ms 34396 KB Output is correct
61 Correct 16 ms 32092 KB Output is correct
62 Correct 14 ms 34396 KB Output is correct
63 Correct 15 ms 34344 KB Output is correct
64 Correct 14 ms 34396 KB Output is correct
65 Correct 13 ms 32088 KB Output is correct
66 Correct 14 ms 34136 KB Output is correct
67 Correct 175 ms 85240 KB Output is correct
68 Correct 92 ms 51508 KB Output is correct
69 Correct 194 ms 83220 KB Output is correct
70 Correct 192 ms 79808 KB Output is correct
71 Correct 203 ms 84148 KB Output is correct
72 Correct 116 ms 54588 KB Output is correct
73 Correct 152 ms 81188 KB Output is correct
74 Correct 177 ms 79032 KB Output is correct
75 Correct 109 ms 52540 KB Output is correct
76 Correct 107 ms 52540 KB Output is correct
77 Correct 86 ms 50460 KB Output is correct
78 Correct 91 ms 50492 KB Output is correct
79 Correct 169 ms 83224 KB Output is correct
80 Correct 129 ms 82360 KB Output is correct
81 Correct 329 ms 82884 KB Output is correct
82 Correct 312 ms 78516 KB Output is correct
83 Correct 113 ms 52028 KB Output is correct
84 Correct 87 ms 50544 KB Output is correct
85 Correct 318 ms 83944 KB Output is correct
86 Correct 168 ms 83380 KB Output is correct
87 Correct 176 ms 83384 KB Output is correct
88 Correct 167 ms 73652 KB Output is correct
89 Correct 169 ms 61880 KB Output is correct
90 Correct 208 ms 63528 KB Output is correct
91 Correct 204 ms 64032 KB Output is correct
92 Correct 218 ms 63804 KB Output is correct
93 Correct 143 ms 53048 KB Output is correct
94 Correct 117 ms 53048 KB Output is correct
95 Correct 102 ms 53564 KB Output is correct
96 Correct 101 ms 58684 KB Output is correct
97 Correct 139 ms 55264 KB Output is correct
98 Correct 110 ms 52024 KB Output is correct
99 Correct 154 ms 60964 KB Output is correct
100 Correct 90 ms 53072 KB Output is correct
101 Correct 341 ms 80316 KB Output is correct
102 Correct 116 ms 48936 KB Output is correct
103 Correct 316 ms 75708 KB Output is correct
104 Correct 345 ms 83636 KB Output is correct