답안 #711697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711697	2023-03-17T11:18:21 Z	hpesoj	Stranded Far From Home (BOI22_island)	C++17	100 / 100	283 ms	43792 KB

island

#include <bits/stdc++.h>
#define int long long
#define pi pair <int, int>
#define ppi pair <pi, int>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << '\n'
#define debug2(x, y) cout << #x << ": " << x << ' ' << #y << ": " << y << '\n'
#define debug3(x, y, z) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << '\n'
#define debug4(x, y, z, w) cout << #x << ": " << x << ' ' << #y << ": " << y << ' ' << #z << ": " << z << ' ' << #w << ": " << w << '\n'
using namespace std;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

const int inf = 1000000000000000000, mod = 998244353;
int n, m, root[200005], val[200005];
pi s[200005];
vector <int> nodes[200005];
vector <int> adj[200005];
bool processed[200005], ans[200005];
int getroot(int x){
	if(x == root[x]) return x;
	else return root[x] = getroot(root[x]);
}
void merge(int x, int y){
	int rootx = getroot(x), rooty = getroot(y);
	//debug4(x, rootx, y, rooty);
	if(rootx == rooty) return;
	if(nodes[rootx].size() < nodes[rooty].size()) swap(rootx, rooty);
	root[rooty] = rootx, val[rootx] += val[rooty];
	for(auto it = nodes[rooty].begin(); it != nodes[rooty].end(); it++) nodes[rootx].pb(*it);
	nodes[rooty].clear();
	//cout << "merged: " << x << ", " << y << '\n';
}
void mark(int x){
	for(auto it = nodes[x].begin(); it != nodes[x].end(); it++) ans[*it] = 0;
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	fill(ans+1, ans+n+1, 0);
	for(int i = 1; i <= n; i++){
		cin >> s[i].fi;
		s[i].se = i, root[i] = i, val[i] = s[i].fi;
		nodes[i].pb(i);
	}
	for(int i = 1; i <= m; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	sort(s+1, s+n+1);
	for(int i = 1; i <= n; i++){
		processed[s[i].se] = 1;
		for(int j : adj[s[i].se]){
			//debug3(s[i].se, j, processed[j]);
			if(!processed[j]) continue;
			int k = getroot(j);
			//debug4(s[i].se, s[i].fi, k, val[k]);
			if(s[i].fi > val[k]){
				nodes[k].clear();
			}
			merge(s[i].se, k);
		}
	}
	for(int i = 1; i <= n; i++){
		if(i != getroot(i)) continue;
		for(auto it = nodes[i].begin(); it != nodes[i].end(); it++) ans[*it] = 1;
	}
	for(int i = 1; i <= n; i++) cout << ans[i];
}
	

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9740 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	9940 KB	Output is correct
5	Correct	7 ms	9940 KB	Output is correct
6	Correct	6 ms	9920 KB	Output is correct
7	Correct	6 ms	9940 KB	Output is correct
8	Correct	6 ms	9812 KB	Output is correct
9	Correct	6 ms	9940 KB	Output is correct
10	Correct	7 ms	9940 KB	Output is correct
11	Correct	6 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	8 ms	9940 KB	Output is correct
14	Correct	7 ms	9940 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	148 ms	32568 KB	Output is correct
4	Correct	160 ms	34792 KB	Output is correct
5	Correct	225 ms	37624 KB	Output is correct
6	Correct	190 ms	40032 KB	Output is correct
7	Correct	192 ms	40016 KB	Output is correct
8	Correct	197 ms	36400 KB	Output is correct
9	Correct	173 ms	43792 KB	Output is correct
10	Correct	118 ms	34212 KB	Output is correct
11	Correct	144 ms	36824 KB	Output is correct
12	Correct	199 ms	35300 KB	Output is correct
13	Correct	142 ms	33876 KB	Output is correct
14	Correct	150 ms	34068 KB	Output is correct
15	Correct	166 ms	35536 KB	Output is correct
16	Correct	96 ms	34512 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	208 ms	36144 KB	Output is correct
3	Correct	212 ms	36456 KB	Output is correct
4	Correct	174 ms	31076 KB	Output is correct
5	Correct	149 ms	33984 KB	Output is correct
6	Correct	212 ms	40652 KB	Output is correct
7	Correct	181 ms	35460 KB	Output is correct
8	Correct	162 ms	35452 KB	Output is correct
9	Correct	97 ms	34564 KB	Output is correct
10	Correct	139 ms	33820 KB	Output is correct
11	Correct	174 ms	34744 KB	Output is correct

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	214 ms	33224 KB	Output is correct
3	Correct	244 ms	36592 KB	Output is correct
4	Correct	244 ms	38756 KB	Output is correct
5	Correct	283 ms	40752 KB	Output is correct
6	Correct	203 ms	36920 KB	Output is correct
7	Correct	137 ms	36220 KB	Output is correct
8	Correct	104 ms	35528 KB	Output is correct
9	Correct	115 ms	25844 KB	Output is correct
10	Correct	197 ms	42224 KB	Output is correct
11	Correct	209 ms	34396 KB	Output is correct

Subtask #5

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9740 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	9940 KB	Output is correct
5	Correct	7 ms	9940 KB	Output is correct
6	Correct	6 ms	9920 KB	Output is correct
7	Correct	6 ms	9940 KB	Output is correct
8	Correct	6 ms	9812 KB	Output is correct
9	Correct	6 ms	9940 KB	Output is correct
10	Correct	7 ms	9940 KB	Output is correct
11	Correct	6 ms	9940 KB	Output is correct
12	Correct	6 ms	9940 KB	Output is correct
13	Correct	8 ms	9940 KB	Output is correct
14	Correct	7 ms	9940 KB	Output is correct
15	Correct	6 ms	9684 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	148 ms	32568 KB	Output is correct
18	Correct	160 ms	34792 KB	Output is correct
19	Correct	225 ms	37624 KB	Output is correct
20	Correct	190 ms	40032 KB	Output is correct
21	Correct	192 ms	40016 KB	Output is correct
22	Correct	197 ms	36400 KB	Output is correct
23	Correct	173 ms	43792 KB	Output is correct
24	Correct	118 ms	34212 KB	Output is correct
25	Correct	144 ms	36824 KB	Output is correct
26	Correct	199 ms	35300 KB	Output is correct
27	Correct	142 ms	33876 KB	Output is correct
28	Correct	150 ms	34068 KB	Output is correct
29	Correct	166 ms	35536 KB	Output is correct
30	Correct	96 ms	34512 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	208 ms	36144 KB	Output is correct
33	Correct	212 ms	36456 KB	Output is correct
34	Correct	174 ms	31076 KB	Output is correct
35	Correct	149 ms	33984 KB	Output is correct
36	Correct	212 ms	40652 KB	Output is correct
37	Correct	181 ms	35460 KB	Output is correct
38	Correct	162 ms	35452 KB	Output is correct
39	Correct	97 ms	34564 KB	Output is correct
40	Correct	139 ms	33820 KB	Output is correct
41	Correct	174 ms	34744 KB	Output is correct
42	Correct	5 ms	9684 KB	Output is correct
43	Correct	214 ms	33224 KB	Output is correct
44	Correct	244 ms	36592 KB	Output is correct
45	Correct	244 ms	38756 KB	Output is correct
46	Correct	283 ms	40752 KB	Output is correct
47	Correct	203 ms	36920 KB	Output is correct
48	Correct	137 ms	36220 KB	Output is correct
49	Correct	104 ms	35528 KB	Output is correct
50	Correct	115 ms	25844 KB	Output is correct
51	Correct	197 ms	42224 KB	Output is correct
52	Correct	209 ms	34396 KB	Output is correct
53	Correct	5 ms	9724 KB	Output is correct
54	Correct	5 ms	9684 KB	Output is correct
55	Correct	7 ms	9660 KB	Output is correct
56	Correct	7 ms	9940 KB	Output is correct
57	Correct	7 ms	9940 KB	Output is correct
58	Correct	8 ms	9864 KB	Output is correct
59	Correct	7 ms	9940 KB	Output is correct
60	Correct	6 ms	9812 KB	Output is correct
61	Correct	6 ms	9996 KB	Output is correct
62	Correct	9 ms	9940 KB	Output is correct
63	Correct	7 ms	10068 KB	Output is correct
64	Correct	7 ms	9940 KB	Output is correct
65	Correct	6 ms	9920 KB	Output is correct
66	Correct	6 ms	9940 KB	Output is correct
67	Correct	156 ms	37032 KB	Output is correct
68	Correct	155 ms	35116 KB	Output is correct
69	Correct	184 ms	38972 KB	Output is correct
70	Correct	193 ms	40144 KB	Output is correct
71	Correct	174 ms	40028 KB	Output is correct
72	Correct	166 ms	36424 KB	Output is correct
73	Correct	177 ms	43748 KB	Output is correct
74	Correct	114 ms	34116 KB	Output is correct
75	Correct	127 ms	36828 KB	Output is correct
76	Correct	191 ms	35276 KB	Output is correct
77	Correct	163 ms	33816 KB	Output is correct
78	Correct	168 ms	34080 KB	Output is correct
79	Correct	160 ms	35468 KB	Output is correct
80	Correct	115 ms	34496 KB	Output is correct
81	Correct	223 ms	40488 KB	Output is correct
82	Correct	216 ms	40868 KB	Output is correct
83	Correct	155 ms	35392 KB	Output is correct
84	Correct	177 ms	34096 KB	Output is correct
85	Correct	226 ms	40636 KB	Output is correct
86	Correct	162 ms	35412 KB	Output is correct
87	Correct	164 ms	35408 KB	Output is correct
88	Correct	149 ms	33856 KB	Output is correct
89	Correct	170 ms	34688 KB	Output is correct
90	Correct	245 ms	37548 KB	Output is correct
91	Correct	222 ms	38220 KB	Output is correct
92	Correct	276 ms	40356 KB	Output is correct
93	Correct	243 ms	42292 KB	Output is correct
94	Correct	203 ms	38488 KB	Output is correct
95	Correct	135 ms	37832 KB	Output is correct
96	Correct	109 ms	36032 KB	Output is correct
97	Correct	127 ms	25872 KB	Output is correct
98	Correct	201 ms	42332 KB	Output is correct
99	Correct	187 ms	34576 KB	Output is correct
100	Correct	43 ms	16372 KB	Output is correct
101	Correct	225 ms	38868 KB	Output is correct
102	Correct	202 ms	34164 KB	Output is correct
103	Correct	203 ms	33192 KB	Output is correct
104	Correct	230 ms	36720 KB	Output is correct