Submission #702214

#	Time	Username	Problem	Language	Result	Execution time	Memory
702214		lovrot	Stranded Far From Home (BOI22_island)	C++17	100 / 100	179 ms	24684 KiB

island

#include <vector>
#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define pb push_back

using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 

const int N = 2e5 + 10; 

int n, m, to[N], U[N], sol[N];
ll S[N], SUM[N];

vector<int> g[N]; 
vector<pair<ll, int>> p; 

int Find(int u) {
	if(u == U[u]) return u; 
	return U[u] = Find(U[u]); 
}

void Union(int u, int v) {
	u = Find(u); 
	v = Find(v); 
	if(u == v) return;
	U[v] = u; 
	SUM[u] += SUM[v]; 
	if(!to[v] || S[to[v]] == S[v]) to[v] = u; 
}

int main() {
	for(int i = 0; i < N; i++) U[i] = i;

	scanf("%d%d", &n, &m); 

	for(int i = 1; i <= n; i++) {
		scanf("%lld", S + i); 
		p.pb({S[i], i}); 
	}

	sort(p.begin(), p.end()); 

	for(int i = 0; i < m; i++) {
		int u, v; 
		scanf("%d%d", &u, &v); 
		if(S[u] < S[v] || S[u] == S[v] && u < v) swap(u, v);
		g[u].pb(v); 
	}

	for(pair<ll, int> u : p) {
		SUM[u.Y] = S[u.Y]; 
		for(int v : g[u.Y]) Union(u.Y, v); 
	}

	reverse(p.begin(), p.end()); 
	to[p[0].Y] = 0; 
	SUM[0] = 0; 
	sol[0] = 1;

	for(pair<ll, int> u : p)
		if(sol[to[u.Y]] && SUM[u.Y] >= S[to[u.Y]]) sol[u.Y] = true; 

	for(int i = 1; i <= n; i++) printf("%d", sol[i]); 
	printf("\n");
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:52:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |   if(S[u] < S[v] || S[u] == S[v] && u < v) swap(u, v);
      |                     ~~~~~~~~~~~~~^~~~~~~~
island.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%lld", S + i);
      |   ~~~~~^~~~~~~~~~~~~~~
island.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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