oj.uz

Submission #949777

# Submission time Handle Problem Language Result Execution time Memory
949777 2024-03-19T16:57:33 Z Dec0Dedd Stranded Far From Home (BOI22_island) C++14
100 / 100
 269 ms 30556 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

const int N = 2e5+10;

vector<int> G[N];
vector<pii> v;

ll n, m, s[N], rep[N];

struct dsu {
    vector<ll> p, sz;

    void init(int k) {
        p.resize(k+10);
        sz.assign(k+10, 0);

        for (int i=0; i<k+10; ++i) p[i]=i, sz[i]=s[i];
    }

    int f(int x) {
        if (p[x] == x) return x;
        return p[x]=f(p[x]);
    }

    void mrg(int x, int y) {
        x=f(x), y=f(y);
        if (x == y) return;
        if (s[y] > s[x]) swap(x, y);
        assert(s[x] >= s[y]);
        sz[x]+=sz[y];
        p[y]=x;
        rep[y]=x;
    }
};

ll idx[N], sm[N];

void solve() {
    cin>>n>>m;

    for (int i=1; i<=n; ++i) {
        cin>>s[i];
        v.push_back({s[i], i});
    } sort(v.begin(), v.end());

    for (int i=0; i<n; ++i) idx[v[i].second]=i;

    for (int i=1; i<=m; ++i) {
        int a, b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    } dsu d; d.init(n+10);

    for (int i=0; i<n; ++i) {
        for (auto u : G[v[i].second]) {
            if (idx[u] < i) d.mrg(v[i].second, u);
        } sm[v[i].second]=d.sz[d.f(v[i].second)];
    }

    bool ans[n+1]={}; ans[v.back().second]=true;
    for (int i=n-2; i>=0; --i) {
        if (ans[rep[v[i].second]] && s[rep[v[i].second]] <= sm[v[i].second]) ans[v[i].second]=true;
    }

    for (int i=1; i<=n; ++i) cout<<ans[i];
    cout<<"\n";
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11220 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 4 ms 11356 KB Output is correct
5 Correct 4 ms 11356 KB Output is correct
6 Correct 4 ms 11352 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct
8 Correct 4 ms 11300 KB Output is correct
9 Correct 3 ms 11356 KB Output is correct
10 Correct 4 ms 11356 KB Output is correct
11 Correct 4 ms 11320 KB Output is correct
12 Correct 4 ms 11352 KB Output is correct
13 Correct 3 ms 11356 KB Output is correct
14 Correct 4 ms 11356 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 196 ms 28724 KB Output is correct
4 Correct 179 ms 28088 KB Output is correct
5 Correct 191 ms 28436 KB Output is correct
6 Correct 207 ms 28716 KB Output is correct
7 Correct 196 ms 28544 KB Output is correct
8 Correct 206 ms 29124 KB Output is correct
9 Correct 185 ms 28856 KB Output is correct
10 Correct 160 ms 28664 KB Output is correct
11 Correct 177 ms 29048 KB Output is correct
12 Correct 176 ms 28344 KB Output is correct
13 Correct 164 ms 29388 KB Output is correct
14 Correct 153 ms 29364 KB Output is correct
15 Correct 180 ms 28600 KB Output is correct
16 Correct 152 ms 27828 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 248 ms 28616 KB Output is correct
3 Correct 265 ms 29156 KB Output is correct
4 Correct 205 ms 29340 KB Output is correct
5 Correct 149 ms 28076 KB Output is correct
6 Correct 235 ms 29640 KB Output is correct
7 Correct 202 ms 28660 KB Output is correct
8 Correct 203 ms 28596 KB Output is correct
9 Correct 161 ms 27740 KB Output is correct
10 Correct 180 ms 29156 KB Output is correct
11 Correct 172 ms 27320 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 238 ms 28840 KB Output is correct
3 Correct 211 ms 28920 KB Output is correct
4 Correct 219 ms 29132 KB Output is correct
5 Correct 223 ms 28852 KB Output is correct
6 Correct 197 ms 27920 KB Output is correct
7 Correct 187 ms 29268 KB Output is correct
8 Correct 152 ms 28504 KB Output is correct
9 Correct 141 ms 21420 KB Output is correct
10 Correct 176 ms 28076 KB Output is correct
11 Correct 171 ms 27320 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 3 ms 11220 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 4 ms 11356 KB Output is correct
5 Correct 4 ms 11356 KB Output is correct
6 Correct 4 ms 11352 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct
8 Correct 4 ms 11300 KB Output is correct
9 Correct 3 ms 11356 KB Output is correct
10 Correct 4 ms 11356 KB Output is correct
11 Correct 4 ms 11320 KB Output is correct
12 Correct 4 ms 11352 KB Output is correct
13 Correct 3 ms 11356 KB Output is correct
14 Correct 4 ms 11356 KB Output is correct
15 Correct 2 ms 11100 KB Output is correct
16 Correct 2 ms 9048 KB Output is correct
17 Correct 196 ms 28724 KB Output is correct
18 Correct 179 ms 28088 KB Output is correct
19 Correct 191 ms 28436 KB Output is correct
20 Correct 207 ms 28716 KB Output is correct
21 Correct 196 ms 28544 KB Output is correct
22 Correct 206 ms 29124 KB Output is correct
23 Correct 185 ms 28856 KB Output is correct
24 Correct 160 ms 28664 KB Output is correct
25 Correct 177 ms 29048 KB Output is correct
26 Correct 176 ms 28344 KB Output is correct
27 Correct 164 ms 29388 KB Output is correct
28 Correct 153 ms 29364 KB Output is correct
29 Correct 180 ms 28600 KB Output is correct
30 Correct 152 ms 27828 KB Output is correct
31 Correct 2 ms 9308 KB Output is correct
32 Correct 248 ms 28616 KB Output is correct
33 Correct 265 ms 29156 KB Output is correct
34 Correct 205 ms 29340 KB Output is correct
35 Correct 149 ms 28076 KB Output is correct
36 Correct 235 ms 29640 KB Output is correct
37 Correct 202 ms 28660 KB Output is correct
38 Correct 203 ms 28596 KB Output is correct
39 Correct 161 ms 27740 KB Output is correct
40 Correct 180 ms 29156 KB Output is correct
41 Correct 172 ms 27320 KB Output is correct
42 Correct 2 ms 9048 KB Output is correct
43 Correct 238 ms 28840 KB Output is correct
44 Correct 211 ms 28920 KB Output is correct
45 Correct 219 ms 29132 KB Output is correct
46 Correct 223 ms 28852 KB Output is correct
47 Correct 197 ms 27920 KB Output is correct
48 Correct 187 ms 29268 KB Output is correct
49 Correct 152 ms 28504 KB Output is correct
50 Correct 141 ms 21420 KB Output is correct
51 Correct 176 ms 28076 KB Output is correct
52 Correct 171 ms 27320 KB Output is correct
53 Correct 3 ms 11100 KB Output is correct
54 Correct 2 ms 11100 KB Output is correct
55 Correct 2 ms 9052 KB Output is correct
56 Correct 3 ms 11556 KB Output is correct
57 Correct 4 ms 11356 KB Output is correct
58 Correct 3 ms 11356 KB Output is correct
59 Correct 3 ms 11356 KB Output is correct
60 Correct 3 ms 11484 KB Output is correct
61 Correct 3 ms 11356 KB Output is correct
62 Correct 4 ms 11356 KB Output is correct
63 Correct 4 ms 11356 KB Output is correct
64 Correct 4 ms 11356 KB Output is correct
65 Correct 4 ms 11356 KB Output is correct
66 Correct 4 ms 11356 KB Output is correct
67 Correct 181 ms 28840 KB Output is correct
68 Correct 180 ms 29068 KB Output is correct
69 Correct 198 ms 28084 KB Output is correct
70 Correct 195 ms 28912 KB Output is correct
71 Correct 203 ms 28796 KB Output is correct
72 Correct 208 ms 29116 KB Output is correct
73 Correct 192 ms 28696 KB Output is correct
74 Correct 171 ms 28652 KB Output is correct
75 Correct 172 ms 28344 KB Output is correct
76 Correct 176 ms 27320 KB Output is correct
77 Correct 185 ms 30556 KB Output is correct
78 Correct 168 ms 29300 KB Output is correct
79 Correct 188 ms 28728 KB Output is correct
80 Correct 151 ms 28804 KB Output is correct
81 Correct 207 ms 28852 KB Output is correct
82 Correct 232 ms 28912 KB Output is correct
83 Correct 213 ms 28732 KB Output is correct
84 Correct 175 ms 27828 KB Output is correct
85 Correct 215 ms 28600 KB Output is correct
86 Correct 215 ms 29628 KB Output is correct
87 Correct 198 ms 28600 KB Output is correct
88 Correct 179 ms 29368 KB Output is correct
89 Correct 174 ms 28344 KB Output is correct
90 Correct 223 ms 28600 KB Output is correct
91 Correct 269 ms 28456 KB Output is correct
92 Correct 240 ms 29244 KB Output is correct
93 Correct 220 ms 28540 KB Output is correct
94 Correct 213 ms 28272 KB Output is correct
95 Correct 195 ms 29588 KB Output is correct
96 Correct 146 ms 28692 KB Output is correct
97 Correct 136 ms 21360 KB Output is correct
98 Correct 193 ms 27872 KB Output is correct
99 Correct 185 ms 27588 KB Output is correct
100 Correct 76 ms 15396 KB Output is correct
101 Correct 225 ms 29112 KB Output is correct
102 Correct 201 ms 25672 KB Output is correct
103 Correct 210 ms 26564 KB Output is correct
104 Correct 256 ms 29388 KB Output is correct