oj.uz

Submission #597935

# Submission time Handle Problem Language Result Execution time Memory
597935 2022-07-17T07:53:05 Z maomao90 Stranded Far From Home (BOI22_island) C++17
100 / 100
 491 ms 79156 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int MAXN = 300005;
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXL = 20;

int n, m;
int s[MAXN];
set<ii> adj[MAXN];
bool vis[MAXN];
int ap[MAXN];
bool ans[MAXN];

ll sm[MAXN];
int p[MAXN], rnk[MAXN];
void init() {
    REP (i, 1, n + 1) {
	sm[i] = s[i];
	p[i] = i;
	rnk[i] = 1;
    }
}
int findp(int i) {
    if (p[i] == i) return i;
    return p[i] = findp(p[i]);
}
bool join(int a, int b) {
    int pa = findp(a), pb = findp(b);
    if (pa == pb) return 0;
    if (rnk[pa] < rnk[pb]) swap(pa, pb);
    if (rnk[pa] == rnk[pb]) rnk[pa]++;
    p[pb] = pa;
    sm[pa] += sm[pb];
    if (adj[pa].size() < adj[pb].size()) {
	swap(adj[pa], adj[pb]);
    }
    for (ii v : adj[pb]) {
	adj[pa].insert(v);
    }
    return 1;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> m;
    REP (i, 1, n + 1) {
	cin >> s[i];
    }
    REP (i, 0, m) {
	int u, v; cin >> u >> v;
	adj[u].insert({s[v], v});
	adj[v].insert({s[u], u});
    }

    init();
    vi id(n, 0);
    iota(ALL(id), 1);
    sort(ALL(id), [&] (int l, int r) {
	    return s[l] < s[r];
	    });
    for (int u : id) {
	vis[u] = 1;
	vi toj;
	for (auto [w, v] : adj[u]) {
	    if (vis[v]) {
		toj.pb(v);
	    }
	}
	cerr << u << '\n';
	for (int v : toj) {
	    cerr << u << " <-> " << v << '\n';
	    join(u, v);
	}
	int fp = findp(u);
	while (!adj[fp].empty() && vis[findp(adj[fp].begin() -> SE)]) {
	    adj[fp].erase(adj[fp].begin());
	}
	ap[u] = -1;
	if (!adj[fp].empty() && sm[fp] >= adj[fp].begin() -> FI) {
	    ap[u] = adj[fp].begin() -> SE;
	}
    }
    reverse(ALL(id));
    ans[id[0]] = 1;
    for (int u : id) {
	cerr << u << ": " << ap[u] << '\n';
	if (ap[u] == -1) continue;
	ans[u] = ans[ap[u]];
    }

    REP (i, 1, n + 1) {
	cout << ans[i];
    }
    cout << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 9 ms 14676 KB Output is correct
6 Correct 9 ms 14828 KB Output is correct
7 Correct 9 ms 14684 KB Output is correct
8 Correct 9 ms 14684 KB Output is correct
9 Correct 10 ms 14804 KB Output is correct
10 Correct 8 ms 14696 KB Output is correct
11 Correct 10 ms 14676 KB Output is correct
12 Correct 8 ms 14688 KB Output is correct
13 Correct 9 ms 14824 KB Output is correct
14 Correct 9 ms 14648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14388 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 208 ms 41424 KB Output is correct
4 Correct 296 ms 67976 KB Output is correct
5 Correct 222 ms 39896 KB Output is correct
6 Correct 236 ms 41184 KB Output is correct
7 Correct 268 ms 41928 KB Output is correct
8 Correct 415 ms 59068 KB Output is correct
9 Correct 215 ms 41548 KB Output is correct
10 Correct 282 ms 43060 KB Output is correct
11 Correct 320 ms 42904 KB Output is correct
12 Correct 331 ms 46764 KB Output is correct
13 Correct 269 ms 70244 KB Output is correct
14 Correct 278 ms 68980 KB Output is correct
15 Correct 191 ms 43068 KB Output is correct
16 Correct 117 ms 41660 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 295 ms 42512 KB Output is correct
3 Correct 293 ms 41984 KB Output is correct
4 Correct 325 ms 79156 KB Output is correct
5 Correct 266 ms 66544 KB Output is correct
6 Correct 287 ms 42560 KB Output is correct
7 Correct 218 ms 42588 KB Output is correct
8 Correct 219 ms 42528 KB Output is correct
9 Correct 112 ms 40660 KB Output is correct
10 Correct 267 ms 59952 KB Output is correct
11 Correct 264 ms 50236 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 358 ms 43168 KB Output is correct
3 Correct 345 ms 44080 KB Output is correct
4 Correct 344 ms 42548 KB Output is correct
5 Correct 491 ms 68388 KB Output is correct
6 Correct 456 ms 59804 KB Output is correct
7 Correct 289 ms 41556 KB Output is correct
8 Correct 220 ms 74924 KB Output is correct
9 Correct 342 ms 41036 KB Output is correct
10 Correct 478 ms 68924 KB Output is correct
11 Correct 272 ms 48960 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 9 ms 14676 KB Output is correct
6 Correct 9 ms 14828 KB Output is correct
7 Correct 9 ms 14684 KB Output is correct
8 Correct 9 ms 14684 KB Output is correct
9 Correct 10 ms 14804 KB Output is correct
10 Correct 8 ms 14696 KB Output is correct
11 Correct 10 ms 14676 KB Output is correct
12 Correct 8 ms 14688 KB Output is correct
13 Correct 9 ms 14824 KB Output is correct
14 Correct 9 ms 14648 KB Output is correct
15 Correct 7 ms 14388 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 208 ms 41424 KB Output is correct
18 Correct 296 ms 67976 KB Output is correct
19 Correct 222 ms 39896 KB Output is correct
20 Correct 236 ms 41184 KB Output is correct
21 Correct 268 ms 41928 KB Output is correct
22 Correct 415 ms 59068 KB Output is correct
23 Correct 215 ms 41548 KB Output is correct
24 Correct 282 ms 43060 KB Output is correct
25 Correct 320 ms 42904 KB Output is correct
26 Correct 331 ms 46764 KB Output is correct
27 Correct 269 ms 70244 KB Output is correct
28 Correct 278 ms 68980 KB Output is correct
29 Correct 191 ms 43068 KB Output is correct
30 Correct 117 ms 41660 KB Output is correct
31 Correct 8 ms 14420 KB Output is correct
32 Correct 295 ms 42512 KB Output is correct
33 Correct 293 ms 41984 KB Output is correct
34 Correct 325 ms 79156 KB Output is correct
35 Correct 266 ms 66544 KB Output is correct
36 Correct 287 ms 42560 KB Output is correct
37 Correct 218 ms 42588 KB Output is correct
38 Correct 219 ms 42528 KB Output is correct
39 Correct 112 ms 40660 KB Output is correct
40 Correct 267 ms 59952 KB Output is correct
41 Correct 264 ms 50236 KB Output is correct
42 Correct 7 ms 14424 KB Output is correct
43 Correct 358 ms 43168 KB Output is correct
44 Correct 345 ms 44080 KB Output is correct
45 Correct 344 ms 42548 KB Output is correct
46 Correct 491 ms 68388 KB Output is correct
47 Correct 456 ms 59804 KB Output is correct
48 Correct 289 ms 41556 KB Output is correct
49 Correct 220 ms 74924 KB Output is correct
50 Correct 342 ms 41036 KB Output is correct
51 Correct 478 ms 68924 KB Output is correct
52 Correct 272 ms 48960 KB Output is correct
53 Correct 7 ms 14420 KB Output is correct
54 Correct 9 ms 14420 KB Output is correct
55 Correct 7 ms 14420 KB Output is correct
56 Correct 9 ms 14676 KB Output is correct
57 Correct 9 ms 14720 KB Output is correct
58 Correct 9 ms 14824 KB Output is correct
59 Correct 8 ms 14688 KB Output is correct
60 Correct 9 ms 14676 KB Output is correct
61 Correct 10 ms 14888 KB Output is correct
62 Correct 8 ms 14676 KB Output is correct
63 Correct 9 ms 14676 KB Output is correct
64 Correct 8 ms 14616 KB Output is correct
65 Correct 9 ms 14820 KB Output is correct
66 Correct 9 ms 14680 KB Output is correct
67 Correct 212 ms 42128 KB Output is correct
68 Correct 303 ms 68236 KB Output is correct
69 Correct 232 ms 39328 KB Output is correct
70 Correct 241 ms 41324 KB Output is correct
71 Correct 233 ms 40664 KB Output is correct
72 Correct 433 ms 58836 KB Output is correct
73 Correct 222 ms 41744 KB Output is correct
74 Correct 291 ms 41272 KB Output is correct
75 Correct 296 ms 41556 KB Output is correct
76 Correct 344 ms 46144 KB Output is correct
77 Correct 277 ms 70088 KB Output is correct
78 Correct 282 ms 67832 KB Output is correct
79 Correct 190 ms 41816 KB Output is correct
80 Correct 112 ms 42428 KB Output is correct
81 Correct 287 ms 41408 KB Output is correct
82 Correct 316 ms 42276 KB Output is correct
83 Correct 315 ms 75212 KB Output is correct
84 Correct 263 ms 66084 KB Output is correct
85 Correct 289 ms 43728 KB Output is correct
86 Correct 222 ms 43592 KB Output is correct
87 Correct 216 ms 43476 KB Output is correct
88 Correct 278 ms 59280 KB Output is correct
89 Correct 269 ms 47892 KB Output is correct
90 Correct 357 ms 43724 KB Output is correct
91 Correct 364 ms 45508 KB Output is correct
92 Correct 361 ms 45644 KB Output is correct
93 Correct 476 ms 67668 KB Output is correct
94 Correct 447 ms 59992 KB Output is correct
95 Correct 307 ms 43464 KB Output is correct
96 Correct 231 ms 74532 KB Output is correct
97 Correct 383 ms 41444 KB Output is correct
98 Correct 468 ms 70604 KB Output is correct
99 Correct 264 ms 50344 KB Output is correct
100 Correct 325 ms 35348 KB Output is correct
101 Correct 346 ms 43596 KB Output is correct
102 Correct 449 ms 56760 KB Output is correct
103 Correct 375 ms 43212 KB Output is correct
104 Correct 356 ms 41220 KB Output is correct