Submission #974290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
974290	2024-05-03T07:31:29 Z	Circling	Stranded Far From Home (BOI22_island)	C++17	100 / 100	343 ms	72220 KB

island

/*The British Royal Family and a small cadre of English Fabian Socialists, in
conjunction with the Rockefellers and the Rothchilds, are engaged in a
conspiracy to greatly reduce the population of the human race in order to head
off a Malthusian catastrophe, a catastrophe that could easily be avoided by
simply building a massive amount of nuclear power plants and a number of massive
superhighways and bridges to connect all of the world's continents. But doing
that would cut into the conspiracy's profits. So the British Royal Family
invented environmentalism and neoliberalism in order to hide the truth. And in
order to further reduce the population, the British Royal Family is also the
world's foremost drug trafficking conspiracy. And it uses its control of the IMF
to push austerity in order to kill as many people in the global south as
possible.
And also Henry Kissinger is a gay KGB agent. */
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;


int64_t n, m, s[200000], comprep[200000], compsze[200000], compmax[200000], compsum[200000];
pair<int, int> edges[200000];
set<int> compdom[200000];


bool vertcomp(int a, int b){
    if (s[a] != s[b]) return s[a] < s[b];
    return a < b;
}

bool edgecomp(pair<int, int> a, pair<int, int> b){
    if (a.first != b.first) return vertcomp(a.first, b.first);
    return vertcomp(a.second, b.second);
}

int findp(int node){
    if (comprep[comprep[node]] == comprep[node]) return comprep[node];
    comprep[node] = findp(comprep[node]);
    return comprep[node];
}

void unite(int na, int nb){
    int pa = findp(na), pb = findp(nb);
    if (pa == pb) return;
    if (compsze[pb] < compsze[pa]) swap(pa, pb);
    comprep[pa] = pb;
    compsze[pb] += compsze[pa];
    if (compsum[pa] < compmax[pb]) compdom[pa].clear();
    if (compsum[pb] < compmax[pa]) compdom[pb].clear();
    if (compdom[pa].size() > compdom[pb].size()) swap(compdom[pa], compdom[pb]);
    for (int i: compdom[pa]) compdom[pb].insert(i);
    compmax[pb] = max(compmax[pa], compmax[pb]);
    compsum[pb] += compsum[pa];
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> s[i];
        comprep[i] = i;
        compsze[i] = 1;
        compsum[i] = s[i];
        compmax[i] = s[i];
        compdom[i] = {i};
    }
    for (int i = 0; i < m; i++){
        cin >> edges[i].first >> edges[i].second;
        edges[i].first--;
        edges[i].second--;
        if (vertcomp(edges[i].first, edges[i].second)) swap(edges[i].first, edges[i].second);
    }
    sort(edges, edges + m, edgecomp);
    for (int i = 0; i < m; i++) unite(edges[i].first, edges[i].second);
    for (int i = 0; i < n; i++) cout << (compdom[findp(0)].find(i) != compdom[findp(0)].end());
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	19036 KB	Output is correct
2	Correct	4 ms	19032 KB	Output is correct
3	Correct	4 ms	19036 KB	Output is correct
4	Correct	5 ms	19036 KB	Output is correct
5	Correct	5 ms	19292 KB	Output is correct
6	Correct	5 ms	19292 KB	Output is correct
7	Correct	4 ms	19036 KB	Output is correct
8	Correct	5 ms	19036 KB	Output is correct
9	Correct	4 ms	19036 KB	Output is correct
10	Correct	5 ms	19352 KB	Output is correct
11	Correct	5 ms	19288 KB	Output is correct
12	Correct	5 ms	19292 KB	Output is correct
13	Correct	4 ms	19292 KB	Output is correct
14	Correct	5 ms	19304 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	19036 KB	Output is correct
2	Correct	3 ms	19036 KB	Output is correct
3	Correct	125 ms	34248 KB	Output is correct
4	Correct	127 ms	41044 KB	Output is correct
5	Correct	196 ms	49024 KB	Output is correct
6	Correct	207 ms	51280 KB	Output is correct
7	Correct	199 ms	50512 KB	Output is correct
8	Correct	136 ms	42428 KB	Output is correct
9	Correct	162 ms	58368 KB	Output is correct
10	Correct	86 ms	32336 KB	Output is correct
11	Correct	131 ms	41756 KB	Output is correct
12	Correct	137 ms	39312 KB	Output is correct
13	Correct	111 ms	41032 KB	Output is correct
14	Correct	123 ms	41132 KB	Output is correct
15	Correct	144 ms	42704 KB	Output is correct
16	Correct	115 ms	41552 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	19032 KB	Output is correct
2	Correct	236 ms	52972 KB	Output is correct
3	Correct	234 ms	57224 KB	Output is correct
4	Correct	138 ms	42324 KB	Output is correct
5	Correct	111 ms	41044 KB	Output is correct
6	Correct	243 ms	57052 KB	Output is correct
7	Correct	148 ms	42440 KB	Output is correct
8	Correct	148 ms	42440 KB	Output is correct
9	Correct	120 ms	41472 KB	Output is correct
10	Correct	116 ms	32272 KB	Output is correct
11	Correct	132 ms	39528 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	19032 KB	Output is correct
2	Correct	253 ms	39072 KB	Output is correct
3	Correct	249 ms	46536 KB	Output is correct
4	Correct	280 ms	54356 KB	Output is correct
5	Correct	314 ms	67920 KB	Output is correct
6	Correct	259 ms	54204 KB	Output is correct
7	Correct	138 ms	42948 KB	Output is correct
8	Correct	119 ms	36692 KB	Output is correct
9	Correct	103 ms	29404 KB	Output is correct
10	Correct	305 ms	72076 KB	Output is correct
11	Correct	137 ms	39608 KB	Output is correct

Subtask #5

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	19036 KB	Output is correct
2	Correct	4 ms	19032 KB	Output is correct
3	Correct	4 ms	19036 KB	Output is correct
4	Correct	5 ms	19036 KB	Output is correct
5	Correct	5 ms	19292 KB	Output is correct
6	Correct	5 ms	19292 KB	Output is correct
7	Correct	4 ms	19036 KB	Output is correct
8	Correct	5 ms	19036 KB	Output is correct
9	Correct	4 ms	19036 KB	Output is correct
10	Correct	5 ms	19352 KB	Output is correct
11	Correct	5 ms	19288 KB	Output is correct
12	Correct	5 ms	19292 KB	Output is correct
13	Correct	4 ms	19292 KB	Output is correct
14	Correct	5 ms	19304 KB	Output is correct
15	Correct	3 ms	19036 KB	Output is correct
16	Correct	3 ms	19036 KB	Output is correct
17	Correct	125 ms	34248 KB	Output is correct
18	Correct	127 ms	41044 KB	Output is correct
19	Correct	196 ms	49024 KB	Output is correct
20	Correct	207 ms	51280 KB	Output is correct
21	Correct	199 ms	50512 KB	Output is correct
22	Correct	136 ms	42428 KB	Output is correct
23	Correct	162 ms	58368 KB	Output is correct
24	Correct	86 ms	32336 KB	Output is correct
25	Correct	131 ms	41756 KB	Output is correct
26	Correct	137 ms	39312 KB	Output is correct
27	Correct	111 ms	41032 KB	Output is correct
28	Correct	123 ms	41132 KB	Output is correct
29	Correct	144 ms	42704 KB	Output is correct
30	Correct	115 ms	41552 KB	Output is correct
31	Correct	3 ms	19032 KB	Output is correct
32	Correct	236 ms	52972 KB	Output is correct
33	Correct	234 ms	57224 KB	Output is correct
34	Correct	138 ms	42324 KB	Output is correct
35	Correct	111 ms	41044 KB	Output is correct
36	Correct	243 ms	57052 KB	Output is correct
37	Correct	148 ms	42440 KB	Output is correct
38	Correct	148 ms	42440 KB	Output is correct
39	Correct	120 ms	41472 KB	Output is correct
40	Correct	116 ms	32272 KB	Output is correct
41	Correct	132 ms	39528 KB	Output is correct
42	Correct	3 ms	19032 KB	Output is correct
43	Correct	253 ms	39072 KB	Output is correct
44	Correct	249 ms	46536 KB	Output is correct
45	Correct	280 ms	54356 KB	Output is correct
46	Correct	314 ms	67920 KB	Output is correct
47	Correct	259 ms	54204 KB	Output is correct
48	Correct	138 ms	42948 KB	Output is correct
49	Correct	119 ms	36692 KB	Output is correct
50	Correct	103 ms	29404 KB	Output is correct
51	Correct	305 ms	72076 KB	Output is correct
52	Correct	137 ms	39608 KB	Output is correct
53	Correct	4 ms	19032 KB	Output is correct
54	Correct	4 ms	19036 KB	Output is correct
55	Correct	3 ms	19036 KB	Output is correct
56	Correct	4 ms	19036 KB	Output is correct
57	Correct	5 ms	19288 KB	Output is correct
58	Correct	4 ms	19292 KB	Output is correct
59	Correct	4 ms	19036 KB	Output is correct
60	Correct	5 ms	19136 KB	Output is correct
61	Correct	4 ms	19268 KB	Output is correct
62	Correct	5 ms	19292 KB	Output is correct
63	Correct	5 ms	19292 KB	Output is correct
64	Correct	5 ms	19288 KB	Output is correct
65	Correct	4 ms	19292 KB	Output is correct
66	Correct	5 ms	19292 KB	Output is correct
67	Correct	126 ms	38736 KB	Output is correct
68	Correct	127 ms	41296 KB	Output is correct
69	Correct	221 ms	48840 KB	Output is correct
70	Correct	216 ms	51460 KB	Output is correct
71	Correct	241 ms	50620 KB	Output is correct
72	Correct	140 ms	42476 KB	Output is correct
73	Correct	177 ms	58308 KB	Output is correct
74	Correct	93 ms	32216 KB	Output is correct
75	Correct	141 ms	41708 KB	Output is correct
76	Correct	147 ms	39552 KB	Output is correct
77	Correct	114 ms	41040 KB	Output is correct
78	Correct	128 ms	41156 KB	Output is correct
79	Correct	138 ms	42576 KB	Output is correct
80	Correct	115 ms	41496 KB	Output is correct
81	Correct	257 ms	57224 KB	Output is correct
82	Correct	256 ms	57176 KB	Output is correct
83	Correct	142 ms	42568 KB	Output is correct
84	Correct	110 ms	41008 KB	Output is correct
85	Correct	257 ms	56680 KB	Output is correct
86	Correct	145 ms	42576 KB	Output is correct
87	Correct	145 ms	42568 KB	Output is correct
88	Correct	127 ms	32440 KB	Output is correct
89	Correct	131 ms	39456 KB	Output is correct
90	Correct	248 ms	43344 KB	Output is correct
91	Correct	249 ms	46312 KB	Output is correct
92	Correct	291 ms	54348 KB	Output is correct
93	Correct	343 ms	68072 KB	Output is correct
94	Correct	271 ms	54096 KB	Output is correct
95	Correct	137 ms	42580 KB	Output is correct
96	Correct	122 ms	36692 KB	Output is correct
97	Correct	103 ms	29532 KB	Output is correct
98	Correct	307 ms	72220 KB	Output is correct
99	Correct	134 ms	39536 KB	Output is correct
100	Correct	54 ms	21312 KB	Output is correct
101	Correct	243 ms	47320 KB	Output is correct
102	Correct	175 ms	43724 KB	Output is correct
103	Correct	186 ms	35152 KB	Output is correct
104	Correct	251 ms	40020 KB	Output is correct