oj.uz

Submission #975091

# Submission time Handle Problem Language Result Execution time Memory
975091 2024-05-04T12:19:35 Z c2zi6 Stranded Far From Home (BOI22_island) C++14
100 / 100
 214 ms 53308 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

VI par, cnt;
VL sumc;
int get(int u) {
	return par[u] = (u == par[u] ? u : get(par[u]));
}
void join(int u, int v) {
	u = get(u);
	v = get(v);
	if (u == v) return;
	if (cnt[u] < cnt[v]) swap(u, v);
	par[v] = u;
	cnt[u] += cnt[v];
	sumc[u] += sumc[v];
}

VI s;

VVI tr;
VI ans;
VL sum;
void dfs(int u, int p = -1) {
	ans[u] = true;
	if (p != -1 && s[p] > sum[u]) ans[u] = false;
	if (p != -1 && ans[p] == false) ans[u] = false;
	for (int v : tr[u]) dfs(v, u);
}

void solve() {
	int n, m;
	cin >> n >> m;
	s = VI(n);
	for (int& x : s) cin >> x;
	VVI gp(n);
	rep(i, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		gp[u].pb(v);
		gp[v].pb(u);
	}
	VI ord;
	rep(u, n) ord.pb(u);
	sort(all(ord), [&](int a, int b){return s[a] < s[b];});
	VVI order;
	rep(i, n) {
		if (i == 0 || s[ord[i]] != s[ord[i-1]]) order.pb(VI());
		order.back().pb(ord[i]);
	}
	par = cnt = VI(n, 1);
	sumc = VL(n);
	rep(i, n) {
		par[i] = i;
		sumc[i] = s[i];
	}
	sum = VL(n);	// for one node
	VI mx(n);   // for one component
	rep(i, n) {
		sum[i] = s[i];
		mx[i] = i;
	}
	tr = VVI(n);
	for (VI ord : order) {
		for (int u : ord) for (int v : gp[u]) if (s[v] <= s[u]) if (get(u) != get(v)) {
			tr[u].pb(mx[get(v)]);
			int m = mx[get(u)];
			join(u, v);
			mx[get(u)] = m;
		}
		for (int u : ord) sum[u] = sumc[get(u)];
	}
	ans = VI(n, -1);
	dfs(mx[get(0)]);
	for (int x : ans) if (x == -1) {
		ans = VI(n, 0);
		break;
	}
	for (int x : ans) cout << x;
	cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /* cin >> t; */
    while (t--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 760 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 139 ms 47288 KB Output is correct
4 Correct 120 ms 33920 KB Output is correct
5 Correct 155 ms 43496 KB Output is correct
6 Correct 149 ms 41268 KB Output is correct
7 Correct 168 ms 44480 KB Output is correct
8 Correct 143 ms 34848 KB Output is correct
9 Correct 120 ms 41144 KB Output is correct
10 Correct 105 ms 38780 KB Output is correct
11 Correct 112 ms 41544 KB Output is correct
12 Correct 160 ms 32400 KB Output is correct
13 Correct 108 ms 39180 KB Output is correct
14 Correct 115 ms 37504 KB Output is correct
15 Correct 142 ms 53280 KB Output is correct
16 Correct 114 ms 51512 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 213 ms 44392 KB Output is correct
3 Correct 193 ms 41436 KB Output is correct
4 Correct 120 ms 39324 KB Output is correct
5 Correct 139 ms 35640 KB Output is correct
6 Correct 214 ms 43936 KB Output is correct
7 Correct 155 ms 53308 KB Output is correct
8 Correct 158 ms 53084 KB Output is correct
9 Correct 102 ms 51644 KB Output is correct
10 Correct 123 ms 37824 KB Output is correct
11 Correct 156 ms 32448 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 170 ms 33728 KB Output is correct
3 Correct 167 ms 33224 KB Output is correct
4 Correct 182 ms 33668 KB Output is correct
5 Correct 141 ms 33460 KB Output is correct
6 Correct 152 ms 32920 KB Output is correct
7 Correct 108 ms 40924 KB Output is correct
8 Correct 97 ms 39620 KB Output is correct
9 Correct 78 ms 18636 KB Output is correct
10 Correct 188 ms 32048 KB Output is correct
11 Correct 122 ms 32112 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 760 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 139 ms 47288 KB Output is correct
18 Correct 120 ms 33920 KB Output is correct
19 Correct 155 ms 43496 KB Output is correct
20 Correct 149 ms 41268 KB Output is correct
21 Correct 168 ms 44480 KB Output is correct
22 Correct 143 ms 34848 KB Output is correct
23 Correct 120 ms 41144 KB Output is correct
24 Correct 105 ms 38780 KB Output is correct
25 Correct 112 ms 41544 KB Output is correct
26 Correct 160 ms 32400 KB Output is correct
27 Correct 108 ms 39180 KB Output is correct
28 Correct 115 ms 37504 KB Output is correct
29 Correct 142 ms 53280 KB Output is correct
30 Correct 114 ms 51512 KB Output is correct
31 Correct 1 ms 456 KB Output is correct
32 Correct 213 ms 44392 KB Output is correct
33 Correct 193 ms 41436 KB Output is correct
34 Correct 120 ms 39324 KB Output is correct
35 Correct 139 ms 35640 KB Output is correct
36 Correct 214 ms 43936 KB Output is correct
37 Correct 155 ms 53308 KB Output is correct
38 Correct 158 ms 53084 KB Output is correct
39 Correct 102 ms 51644 KB Output is correct
40 Correct 123 ms 37824 KB Output is correct
41 Correct 156 ms 32448 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 170 ms 33728 KB Output is correct
44 Correct 167 ms 33224 KB Output is correct
45 Correct 182 ms 33668 KB Output is correct
46 Correct 141 ms 33460 KB Output is correct
47 Correct 152 ms 32920 KB Output is correct
48 Correct 108 ms 40924 KB Output is correct
49 Correct 97 ms 39620 KB Output is correct
50 Correct 78 ms 18636 KB Output is correct
51 Correct 188 ms 32048 KB Output is correct
52 Correct 122 ms 32112 KB Output is correct
53 Correct 1 ms 344 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 2 ms 604 KB Output is correct
57 Correct 2 ms 860 KB Output is correct
58 Correct 2 ms 856 KB Output is correct
59 Correct 1 ms 604 KB Output is correct
60 Correct 2 ms 604 KB Output is correct
61 Correct 2 ms 604 KB Output is correct
62 Correct 1 ms 860 KB Output is correct
63 Correct 2 ms 860 KB Output is correct
64 Correct 2 ms 604 KB Output is correct
65 Correct 2 ms 604 KB Output is correct
66 Correct 2 ms 604 KB Output is correct
67 Correct 131 ms 47032 KB Output is correct
68 Correct 117 ms 33816 KB Output is correct
69 Correct 150 ms 42308 KB Output is correct
70 Correct 167 ms 42720 KB Output is correct
71 Correct 168 ms 43436 KB Output is correct
72 Correct 146 ms 34912 KB Output is correct
73 Correct 155 ms 40524 KB Output is correct
74 Correct 109 ms 39468 KB Output is correct
75 Correct 108 ms 41488 KB Output is correct
76 Correct 170 ms 32396 KB Output is correct
77 Correct 108 ms 39224 KB Output is correct
78 Correct 140 ms 37540 KB Output is correct
79 Correct 145 ms 52200 KB Output is correct
80 Correct 111 ms 51900 KB Output is correct
81 Correct 204 ms 43392 KB Output is correct
82 Correct 208 ms 42936 KB Output is correct
83 Correct 150 ms 39468 KB Output is correct
84 Correct 111 ms 35636 KB Output is correct
85 Correct 194 ms 43688 KB Output is correct
86 Correct 174 ms 53116 KB Output is correct
87 Correct 156 ms 52572 KB Output is correct
88 Correct 122 ms 37312 KB Output is correct
89 Correct 130 ms 32456 KB Output is correct
90 Correct 151 ms 33664 KB Output is correct
91 Correct 164 ms 33476 KB Output is correct
92 Correct 182 ms 33440 KB Output is correct
93 Correct 140 ms 33596 KB Output is correct
94 Correct 133 ms 32560 KB Output is correct
95 Correct 107 ms 40884 KB Output is correct
96 Correct 94 ms 39496 KB Output is correct
97 Correct 83 ms 18636 KB Output is correct
98 Correct 135 ms 32064 KB Output is correct
99 Correct 118 ms 31916 KB Output is correct
100 Correct 30 ms 4948 KB Output is correct
101 Correct 203 ms 42692 KB Output is correct
102 Correct 111 ms 27184 KB Output is correct
103 Correct 161 ms 36584 KB Output is correct
104 Correct 202 ms 44248 KB Output is correct