Submission #628956

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
628956	2022-08-13 21:26:01	peti1234	Thousands Islands (IOI22_islands)	C++17	100 / 100	710 ms	38592 KiB

islands

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
//#include "islands.h"
 
bool test=0;
 
 
using namespace std;
const int c=300005, k=20;
int n, m, szint[c], fel[c], felel[c], fel2[c][k], bal[c], jobb[c], kezd, veg, specid;
vector<int> alaput, alapkor, ans, ut2;
vector<pair<int, int> > sz[c];
bool kesz, v[c], v2[c][2], korben[c], uton[c];
void nullazas() {
    for (int i=1; i<=n; i++) {
        szint[i]=0, fel[i]=0, felel[i]=0;
        v[i]=0, v2[i][0]=0, v2[i][1]=0, korben[i]=0, uton[i]=0;
        for (int j=0; j<k; j++) fel2[i][j]=0;
    }
    alaput.clear(), alapkor.clear(), ans.clear(), ut2.clear();
    kezd=0, veg=0, specid=0;
}
int lca(int a, int b) {
    if (szint[a]<szint[b]) swap(a, b);
    for (int i=k-1; i>=0; i--) {
        if (szint[fel2[a][i]]>=szint[b]) a=fel2[a][i];
    }
    for (int i=k-1; i>=0; i--) {
        if (fel2[a][i]!=fel2[b][i]) {
            a=fel2[a][i], b=fel2[b][i];
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45