Submission #578209

#	Time	Username	Problem	Language	Result	Execution time	Memory
578209		IvanJ	Stranded Far From Home (BOI22_island)	C++17	100 / 100	183 ms	25508 KiB

island

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;

int n, m, P;
ll S[maxn];
int par[maxn];
ll M[maxn];
vector<int> W[maxn];
vector<pair<pair<ll, ll>, ii>> E;
int ans[maxn];

int find(int x) {return (par[x] == x) ? x : par[x] = find(par[x]);}

void merge(int x, int y) {
	x = find(x), y = find(y);
	if(x == y) return;
	if(W[x].size() < W[y].size()) 
		swap(x, y);
	
	if(S[x] < M[y]) W[x].clear();
	if(S[y] < M[x]) W[y].clear();
	for(int i : W[y]) 
		W[x].pb(i);
	
	par[y] = x;
	M[x] = max(M[x], M[y]);
	S[x] += S[y];
	P = x;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0;i < n;i++)
		scanf("%lld", S + i);
	for(int i = 0;i < m;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		x--, y--;
		if(S[x] < S[y]) swap(x, y);
		E.pb({{S[x], S[y]}, {x, y}});
	}
	sort(all(E));
	
	for(int i = 0;i < n;i++)
		par[i] = i, M[i] = S[i], W[i].pb(i);

	
	for(auto p : E)
		merge(p.y.x, p.y.y);
	
	for(int i : W[P]) ans[i] = 1;
	for(int i = 0;i < n;i++)
		printf("%d", ans[i]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%lld", S + i);
      |   ~~~~~^~~~~~~~~~~~~~~
island.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35