Submission #967606

#	Time	Username	Problem	Language	Result	Execution time	Memory
967606		dong_gas	Stranded Far From Home (BOI22_island)	C++17	0 / 100	468 ms	60236 KiB

island

#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll n, m, a[200020];

struct disjoin_set{
	ll papa[200020], height[200020], sum[200020];
	void init() {
		memset(papa,-1,sizeof(papa));
		memset(height,0,sizeof(height));
		for(ll i=1;i<=n;i++) sum[i]=a[i];
	}
	ll Find(ll u) {
		if(papa[u]==-1) return u;
		return papa[u]=Find(papa[u]);
	}
	bool Union(ll u,ll v) {
		u=Find(u), v=Find(v);
		if(u==v) return false;
		if(height[u]<height[v]) swap(u,v);
		papa[v]=u;
		if(height[u]==height[v]) height[u]++;
		sum[u]+=sum[v];
		return true;
	}
} djs;

vector<ll> adj[200020], x;
bool chk[200020], visited[200020];
unordered_map<ll, ll> ma;
map<ll, vector<pll>> edges;

void dfs(ll u, ll p) {
	visited[u]=1;
	for(ll& v:adj[u]) if(!chk[v] && v!=p && !visited[v]) dfs(v, u);
}

void solve() {
    cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i], x.emplace_back(a[i]);
	zip(x), x.emplace_back(0);
	for(ll i=0;i+1<x.size();i++) ma[x[i]]=x[i+1];
	while(m --> 0) {
		ll u, v; cin>>u>>v;
		if(u>v) swap(u,v);
		if(a[u]<a[v]) swap(u,v);
		edges[a[u]].emplace_back(u,v);
		edges[a[v]].emplace_back(v,v);
	}
	djs.init();

	for(auto [p, vec]: edges) {
		//cout<<p<<'\n';
		//for(auto [u,v]:vec) cout<<u<<' '<<v<<endl;
		//cout<<endl;
		ll nxt_val=ma[p];
		set<ll> s;
		for(auto [u, v]: vec) {
			if(djs.Union(u,v)) adj[u].emplace_back(v), adj[v].emplace_back(u);
			s.insert(u), s.insert(v);
		}
		for(auto u: s) {
			if(djs.sum[djs.Find(u)]<nxt_val) chk[u]=1;
		}
		//cout<<nxt_val<<endl;
	}
	//for(ll i=1;i<=n;i++) cout<<chk[i];
	//cout<<endl;
	for(ll i=1;i<=n;i++) if(a[i]==x[x.size()-2] && !visited[i]) dfs(i,0);
	for(ll i=1;i<=n;i++) cout<<visited[i];
	
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
} 

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:49:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(ll i=0;i+1<x.size();i++) ma[x[i]]=x[i+1];
      |             ~~~^~~~~~~~~

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