제출 #967598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967598		dong_gas	Stranded Far From Home (BOI22_island)	C++17	0 / 100	519 ms	61820 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) 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);
	for(ll i=0;i<x.size();i++) {
		if(i+1<(ll)x.size()) ma[x[i]]=x[i+1];
		else ma[x[i]]=0;
	}
	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];
		for(auto [u, v]: vec) if(djs.Union(u,v)) adj[u].emplace_back(v), adj[v].emplace_back(u);
		for(auto [u, v]: vec) if(djs.sum[djs.Find(u)]<nxt_val) {
			chk[u]=1;
			//cout<<"Here:";
			//cout<<u<<' '<<v<<' '<<p<<endl;
		}
	}
	//for(ll i=1;i<=n;i++) cout<<chk[i]<<' ';
	//cout<<endl;
	for(ll i=1;i<=n;i++) if(a[i]==x.back() && !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();
} 

컴파일 시 표준 에러 (stderr) 메시지

island.cpp: In function 'void solve()':
island.cpp:49:14: 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<x.size();i++) {
      |             ~^~~~~~~~~

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