oj.uz

Submission #722915

# Submission time Handle Problem Language Result Execution time Memory
722915 2023-04-13T05:33:25 Z sunnat Stranded Far From Home (BOI22_island) C++14
100 / 100
 417 ms 47176 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long
int n;
vector<int> val, sid, id, root, solution;

vector<vector<int> > graph;
vector<vector<int> > tree;

int dsu(int u){
    return root[u] == u ? u : root[u] = dsu(root[u]);
}
void clear_sub_tree(int u){
    if(solution[u] == 0) return;
    solution[u] = 0;
    for(int v:tree[u]) clear_sub_tree(v);
}
void dfs(int u){
    int vl = val[u];
    // cout << "-->" << u << endl;
    for(int v:tree[u]){
        dfs(v);
        val[u] += val[v];
        if(val[v] < vl) clear_sub_tree(v);
    }
    // cout << "<--" << u << endl;
}

signed main(){
    int m;
    cin >> n >> m;
    val.resize(n);
    graph.resize(n);
    tree.resize(n);
    sid.resize(n);
    id.resize(n);
    solution.resize(n, 1);
    
    for(int i = 0; i < n; i ++){
        cin >> val[i];
        sid[i] = i;
    }
    root = sid;
    sort(sid.begin(), sid.end(), [&](int r, int l){return val[r] < val[l];});
    for(int i = 0; i < n; i ++)
        id[sid[i]] = i;

    for(int i = 0, u, v; i < m; i ++){
        cin >> u >> v;
        --u;
        --v;
        if(id[u] > id[v]) swap(u, v);
        graph[v].push_back(u);
    }

    for(int u:sid){
        for(int v:graph[u]){
            if(dsu(u) != dsu(v)){
                tree[u].push_back(dsu(v));
                root[dsu(v)] = u;
            }
        }
    }
    dfs(sid.back());
    for(int x:solution) cout << x;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 528 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 264 ms 31588 KB Output is correct
4 Correct 261 ms 28752 KB Output is correct
5 Correct 271 ms 25308 KB Output is correct
6 Correct 293 ms 26112 KB Output is correct
7 Correct 292 ms 26188 KB Output is correct
8 Correct 265 ms 27736 KB Output is correct
9 Correct 246 ms 24024 KB Output is correct
10 Correct 180 ms 22164 KB Output is correct
11 Correct 190 ms 22116 KB Output is correct
12 Correct 250 ms 26080 KB Output is correct
13 Correct 213 ms 29404 KB Output is correct
14 Correct 230 ms 29348 KB Output is correct
15 Correct 278 ms 42740 KB Output is correct
16 Correct 200 ms 42284 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 345 ms 25928 KB Output is correct
3 Correct 318 ms 26060 KB Output is correct
4 Correct 277 ms 29372 KB Output is correct
5 Correct 225 ms 29460 KB Output is correct
6 Correct 341 ms 26056 KB Output is correct
7 Correct 293 ms 42736 KB Output is correct
8 Correct 291 ms 42708 KB Output is correct
9 Correct 204 ms 42260 KB Output is correct
10 Correct 256 ms 27752 KB Output is correct
11 Correct 259 ms 29236 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 361 ms 26732 KB Output is correct
3 Correct 324 ms 26356 KB Output is correct
4 Correct 417 ms 26192 KB Output is correct
5 Correct 315 ms 26316 KB Output is correct
6 Correct 295 ms 26608 KB Output is correct
7 Correct 221 ms 24256 KB Output is correct
8 Correct 216 ms 36052 KB Output is correct
9 Correct 203 ms 18364 KB Output is correct
10 Correct 275 ms 29132 KB Output is correct
11 Correct 258 ms 29160 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 528 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 264 ms 31588 KB Output is correct
18 Correct 261 ms 28752 KB Output is correct
19 Correct 271 ms 25308 KB Output is correct
20 Correct 293 ms 26112 KB Output is correct
21 Correct 292 ms 26188 KB Output is correct
22 Correct 265 ms 27736 KB Output is correct
23 Correct 246 ms 24024 KB Output is correct
24 Correct 180 ms 22164 KB Output is correct
25 Correct 190 ms 22116 KB Output is correct
26 Correct 250 ms 26080 KB Output is correct
27 Correct 213 ms 29404 KB Output is correct
28 Correct 230 ms 29348 KB Output is correct
29 Correct 278 ms 42740 KB Output is correct
30 Correct 200 ms 42284 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 345 ms 25928 KB Output is correct
33 Correct 318 ms 26060 KB Output is correct
34 Correct 277 ms 29372 KB Output is correct
35 Correct 225 ms 29460 KB Output is correct
36 Correct 341 ms 26056 KB Output is correct
37 Correct 293 ms 42736 KB Output is correct
38 Correct 291 ms 42708 KB Output is correct
39 Correct 204 ms 42260 KB Output is correct
40 Correct 256 ms 27752 KB Output is correct
41 Correct 259 ms 29236 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 361 ms 26732 KB Output is correct
44 Correct 324 ms 26356 KB Output is correct
45 Correct 417 ms 26192 KB Output is correct
46 Correct 315 ms 26316 KB Output is correct
47 Correct 295 ms 26608 KB Output is correct
48 Correct 221 ms 24256 KB Output is correct
49 Correct 216 ms 36052 KB Output is correct
50 Correct 203 ms 18364 KB Output is correct
51 Correct 275 ms 29132 KB Output is correct
52 Correct 258 ms 29160 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Correct 1 ms 212 KB Output is correct
56 Correct 3 ms 468 KB Output is correct
57 Correct 4 ms 564 KB Output is correct
58 Correct 3 ms 468 KB Output is correct
59 Correct 2 ms 468 KB Output is correct
60 Correct 4 ms 424 KB Output is correct
61 Correct 2 ms 568 KB Output is correct
62 Correct 3 ms 596 KB Output is correct
63 Correct 3 ms 568 KB Output is correct
64 Correct 3 ms 468 KB Output is correct
65 Correct 2 ms 596 KB Output is correct
66 Correct 2 ms 468 KB Output is correct
67 Correct 271 ms 36024 KB Output is correct
68 Correct 220 ms 31776 KB Output is correct
69 Correct 307 ms 29516 KB Output is correct
70 Correct 288 ms 30488 KB Output is correct
71 Correct 291 ms 30512 KB Output is correct
72 Correct 314 ms 32184 KB Output is correct
73 Correct 241 ms 28264 KB Output is correct
74 Correct 203 ms 25648 KB Output is correct
75 Correct 183 ms 25556 KB Output is correct
76 Correct 271 ms 28992 KB Output is correct
77 Correct 221 ms 32456 KB Output is correct
78 Correct 229 ms 32404 KB Output is correct
79 Correct 300 ms 47164 KB Output is correct
80 Correct 222 ms 46052 KB Output is correct
81 Correct 325 ms 30364 KB Output is correct
82 Correct 309 ms 30532 KB Output is correct
83 Correct 299 ms 33936 KB Output is correct
84 Correct 234 ms 32356 KB Output is correct
85 Correct 335 ms 30396 KB Output is correct
86 Correct 279 ms 47148 KB Output is correct
87 Correct 297 ms 47176 KB Output is correct
88 Correct 252 ms 27764 KB Output is correct
89 Correct 264 ms 29016 KB Output is correct
90 Correct 330 ms 31200 KB Output is correct
91 Correct 304 ms 30576 KB Output is correct
92 Correct 327 ms 30704 KB Output is correct
93 Correct 315 ms 30728 KB Output is correct
94 Correct 301 ms 30884 KB Output is correct
95 Correct 233 ms 28680 KB Output is correct
96 Correct 201 ms 39344 KB Output is correct
97 Correct 247 ms 18236 KB Output is correct
98 Correct 292 ms 29092 KB Output is correct
99 Correct 248 ms 29112 KB Output is correct
100 Correct 102 ms 5404 KB Output is correct
101 Correct 355 ms 30668 KB Output is correct
102 Correct 239 ms 28796 KB Output is correct
103 Correct 356 ms 29672 KB Output is correct
104 Correct 355 ms 31376 KB Output is correct