Submission #744962

#	Time	Username	Problem	Language	Result	Execution time	Memory
744962		josanneo22	Stranded Far From Home (BOI22_island)	C++17	100 / 100	249 ms	47980 KiB

island

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
#define int long long


char buf[1 << 23], * p1 = buf, * p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd()
{
	int s = 0;
	char ch = getchar(), lst;
	while (ch < '0' || ch>'9') lst = ch, ch = getchar();
	while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return lst == '-' ? -s : s;
}
int num[100];
inline void rt(int x)
{
	if (x < 0) putchar('-'), x = -x;;
	int len = 0;
	do num[len++] = x % 10; while (x /= 10);
	while (len--) putchar(num[len] + '0');
}


const int maxn = 2e5 + 500;
vector<vector<int>> adj(maxn),mrk(maxn);
vector<int> par, sz, s(maxn), inserted(maxn), power(maxn),vis(maxn), win(maxn,1), rep(maxn);
void init(int n) {
	par.resize(n); sz.resize(n);
	for (int i = 0; i < n; i++) {
		par[i] = i;
		sz[i] = 1;
	}
}
int find(int x) {
	if (par[x] == x) return x;
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	par[y] = x;
	sz[x] += sz[y];
	power[x] += power[y];
}
bool same(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return true;
	else return false;
}
//remember to init(n+5) and total_groups=n
void dfs(int u,int flag) {
	win[u] &= flag;
	for (auto& v : mrk[u]) dfs(v, win[u]);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n = rd(), m = rd();
	for (int i = 0; i < n; i++) {
		s[i] = rd(); power[i] = s[i];
	}
	for (int i = 0; i < m; i++) {
		int u = rd(), v = rd(); 
		u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	init(n + 5);
	vector<pii> ord;
	for (int i = 0; i < n; i++) ord.push_back(mp(s[i], i)); 
	sort(ord.begin(), ord.end()); 
	//note that rep[find(v)] is important:
	//due to path compression: leader is the one with largest size not max 
	//need to reset leader to u
	for (auto &t : ord) {
		int u = t.second;
		for (int v : adj[u]) if (inserted[v]) {
			int w = rep[find(v)];
			if (power[find(v)] < s[u]) {
				win[w] = 0;
			}
			if (!vis[w]) { 
				mrk[u].push_back(w);
				vis[w] = 1;
			}
		}
		for (int v : adj[u]) if (inserted[v]) vis[rep[find(v)]] = 0;
		for (int v : adj[u]) if (inserted[v]) unite(u, v);
		rep[find(u)] = u;
		inserted[u] = 1;
	}
	dfs(ord[n-1].second,1);
	for (int i = 0; i < n; i++)rt(win[i]);
}

Compilation message (stderr)

island.cpp: In function 'long long int rd()':
island.cpp:23:20: warning: 'lst' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |  return lst == '-' ? -s : s;
      |         ~~~~~~~~~~~^~~~~~~~

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