oj.uz

Submission #711014

# Submission time Handle Problem Language Result Execution time Memory
711014 2023-03-16T07:12:29 Z ld_minh4354 Stranded Far From Home (BOI22_island) C++17
100 / 100
 368 ms 75516 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"

int n,m,s[200005],ans[200005];
pair<int,pair<int,int>> ed[200005];

int parent[200005],grpsize[200005],sum[200005];
set<int> nodes[200005];

int getroot(int x)
{
	if (x==parent[x]) return x;
	return getroot(parent[x]);
}

void merge(int x,int y,int id)
{
	int root_x=getroot(x);
	int root_y=getroot(y);
	
	if (root_x==root_y) return;
	
	if (sum[root_x]<ed[id].fi)
	{
		for (int u:nodes[root_x]) ans[u]=0;
		while (nodes[root_x].size()>0) nodes[root_x].erase(nodes[root_x].begin());
	}
	
	if (sum[root_y]<ed[id].fi)
	{
		for (int u:nodes[root_y]) ans[u]=0;
		while (nodes[root_y].size()>0) nodes[root_y].erase(nodes[root_y].begin());
	}
	
	if (grpsize[root_x]<grpsize[root_y]) swap(root_x,root_y);
	
	parent[root_y]=root_x;
	grpsize[root_x]+=grpsize[root_y];
	sum[root_x]+=sum[root_y];
	
	for (int u:nodes[root_y]) nodes[root_x].insert(u);
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int i,j;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>s[i];
	for (i=1;i<m+1;i++)
	{
		cin>>ed[i].se.fi>>ed[i].se.se;
		ed[i].fi=max(s[ed[i].se.fi], s[ed[i].se.se]);
	}
	
	sort(ed+1,ed+m+1);
	ed[m+1]={1e18,{0,0}};
	
	for (i=1;i<n+1;i++)
	{
		parent[i]=i;
		grpsize[i]=1;
		sum[i]=s[i];
		ans[i]=1;
		nodes[i].insert(i);
	}
	
	for (i=1;i<m+1;i++) merge(ed[i].se.fi, ed[i].se.se, i);

	for (j=1;j<n+1;j++) cout<<ans[j];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 7 ms 9992 KB Output is correct
5 Correct 7 ms 10068 KB Output is correct
6 Correct 6 ms 9996 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9892 KB Output is correct
9 Correct 6 ms 9996 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 7 ms 10120 KB Output is correct
12 Correct 7 ms 10068 KB Output is correct
13 Correct 6 ms 9968 KB Output is correct
14 Correct 7 ms 10068 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 139 ms 42852 KB Output is correct
4 Correct 129 ms 43732 KB Output is correct
5 Correct 250 ms 50380 KB Output is correct
6 Correct 233 ms 52700 KB Output is correct
7 Correct 272 ms 52200 KB Output is correct
8 Correct 187 ms 43764 KB Output is correct
9 Correct 200 ms 60532 KB Output is correct
10 Correct 113 ms 34340 KB Output is correct
11 Correct 145 ms 43800 KB Output is correct
12 Correct 168 ms 41924 KB Output is correct
13 Correct 149 ms 43740 KB Output is correct
14 Correct 162 ms 43816 KB Output is correct
15 Correct 155 ms 43804 KB Output is correct
16 Correct 122 ms 43476 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9720 KB Output is correct
2 Correct 277 ms 62616 KB Output is correct
3 Correct 261 ms 60660 KB Output is correct
4 Correct 157 ms 43724 KB Output is correct
5 Correct 148 ms 43820 KB Output is correct
6 Correct 276 ms 60116 KB Output is correct
7 Correct 159 ms 43940 KB Output is correct
8 Correct 178 ms 43740 KB Output is correct
9 Correct 138 ms 43400 KB Output is correct
10 Correct 127 ms 34500 KB Output is correct
11 Correct 149 ms 42624 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 310 ms 48272 KB Output is correct
3 Correct 284 ms 49292 KB Output is correct
4 Correct 310 ms 56720 KB Output is correct
5 Correct 368 ms 69616 KB Output is correct
6 Correct 347 ms 56492 KB Output is correct
7 Correct 147 ms 43584 KB Output is correct
8 Correct 120 ms 38960 KB Output is correct
9 Correct 175 ms 29028 KB Output is correct
10 Correct 366 ms 75360 KB Output is correct
11 Correct 152 ms 42412 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 7 ms 9992 KB Output is correct
5 Correct 7 ms 10068 KB Output is correct
6 Correct 6 ms 9996 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9892 KB Output is correct
9 Correct 6 ms 9996 KB Output is correct
10 Correct 6 ms 10068 KB Output is correct
11 Correct 7 ms 10120 KB Output is correct
12 Correct 7 ms 10068 KB Output is correct
13 Correct 6 ms 9968 KB Output is correct
14 Correct 7 ms 10068 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 7 ms 9684 KB Output is correct
17 Correct 139 ms 42852 KB Output is correct
18 Correct 129 ms 43732 KB Output is correct
19 Correct 250 ms 50380 KB Output is correct
20 Correct 233 ms 52700 KB Output is correct
21 Correct 272 ms 52200 KB Output is correct
22 Correct 187 ms 43764 KB Output is correct
23 Correct 200 ms 60532 KB Output is correct
24 Correct 113 ms 34340 KB Output is correct
25 Correct 145 ms 43800 KB Output is correct
26 Correct 168 ms 41924 KB Output is correct
27 Correct 149 ms 43740 KB Output is correct
28 Correct 162 ms 43816 KB Output is correct
29 Correct 155 ms 43804 KB Output is correct
30 Correct 122 ms 43476 KB Output is correct
31 Correct 5 ms 9720 KB Output is correct
32 Correct 277 ms 62616 KB Output is correct
33 Correct 261 ms 60660 KB Output is correct
34 Correct 157 ms 43724 KB Output is correct
35 Correct 148 ms 43820 KB Output is correct
36 Correct 276 ms 60116 KB Output is correct
37 Correct 159 ms 43940 KB Output is correct
38 Correct 178 ms 43740 KB Output is correct
39 Correct 138 ms 43400 KB Output is correct
40 Correct 127 ms 34500 KB Output is correct
41 Correct 149 ms 42624 KB Output is correct
42 Correct 5 ms 9684 KB Output is correct
43 Correct 310 ms 48272 KB Output is correct
44 Correct 284 ms 49292 KB Output is correct
45 Correct 310 ms 56720 KB Output is correct
46 Correct 368 ms 69616 KB Output is correct
47 Correct 347 ms 56492 KB Output is correct
48 Correct 147 ms 43584 KB Output is correct
49 Correct 120 ms 38960 KB Output is correct
50 Correct 175 ms 29028 KB Output is correct
51 Correct 366 ms 75360 KB Output is correct
52 Correct 152 ms 42412 KB Output is correct
53 Correct 5 ms 9724 KB Output is correct
54 Correct 5 ms 9724 KB Output is correct
55 Correct 5 ms 9724 KB Output is correct
56 Correct 6 ms 9940 KB Output is correct
57 Correct 7 ms 10068 KB Output is correct
58 Correct 7 ms 10028 KB Output is correct
59 Correct 6 ms 9940 KB Output is correct
60 Correct 6 ms 9948 KB Output is correct
61 Correct 6 ms 9992 KB Output is correct
62 Correct 7 ms 10068 KB Output is correct
63 Correct 8 ms 10168 KB Output is correct
64 Correct 7 ms 10068 KB Output is correct
65 Correct 8 ms 9992 KB Output is correct
66 Correct 8 ms 10044 KB Output is correct
67 Correct 141 ms 40988 KB Output is correct
68 Correct 137 ms 43744 KB Output is correct
69 Correct 300 ms 50368 KB Output is correct
70 Correct 242 ms 52648 KB Output is correct
71 Correct 264 ms 52144 KB Output is correct
72 Correct 199 ms 43736 KB Output is correct
73 Correct 223 ms 60468 KB Output is correct
74 Correct 124 ms 34332 KB Output is correct
75 Correct 148 ms 43724 KB Output is correct
76 Correct 191 ms 41932 KB Output is correct
77 Correct 154 ms 43800 KB Output is correct
78 Correct 145 ms 43772 KB Output is correct
79 Correct 150 ms 43812 KB Output is correct
80 Correct 130 ms 43712 KB Output is correct
81 Correct 273 ms 60828 KB Output is correct
82 Correct 284 ms 60692 KB Output is correct
83 Correct 172 ms 43792 KB Output is correct
84 Correct 137 ms 43792 KB Output is correct
85 Correct 274 ms 60188 KB Output is correct
86 Correct 151 ms 43788 KB Output is correct
87 Correct 163 ms 43708 KB Output is correct
88 Correct 132 ms 34424 KB Output is correct
89 Correct 137 ms 42580 KB Output is correct
90 Correct 290 ms 46436 KB Output is correct
91 Correct 299 ms 49472 KB Output is correct
92 Correct 332 ms 56916 KB Output is correct
93 Correct 350 ms 69748 KB Output is correct
94 Correct 301 ms 56524 KB Output is correct
95 Correct 143 ms 43884 KB Output is correct
96 Correct 139 ms 39056 KB Output is correct
97 Correct 149 ms 29056 KB Output is correct
98 Correct 353 ms 75516 KB Output is correct
99 Correct 143 ms 42552 KB Output is correct
100 Correct 61 ms 16816 KB Output is correct
101 Correct 267 ms 50512 KB Output is correct
102 Correct 224 ms 45308 KB Output is correct
103 Correct 201 ms 36756 KB Output is correct
104 Correct 250 ms 42836 KB Output is correct