Submission #682172

#	Time	Username	Problem	Language	Result	Execution time	Memory
682172		jamezzz	Stranded Far From Home (BOI22_island)	C++17	100 / 100	193 ms	24424 KiB

island

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 200005

int n,m,s[maxn],p[maxn],rnk[maxn];
ll tot[maxn];
bool good[maxn];
vi ans[maxn];
vii EL;

int fp(int i){
	return p[i]==i?i:p[i]=fp(p[i]);
}

int join(int x,int y){
	x=fp(x),y=fp(y);
	if(rnk[x]<rnk[y])p[x]=y;
	else p[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
	return p[x];
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=0;i<n;++i){
		sf("%d",&s[i]);
		ans[i].pb(i);
		p[i]=i,rnk[i]=0;
		tot[i]=s[i];
	}
	for(int i=0;i<m;++i){
		int a,b;
		sf("%d%d",&a,&b);
		--a,--b;
		if(s[a]>s[b])swap(a,b);
		EL.pb({a,b});
	}
	sort(all(EL),[&](ii &a,ii &b){
		return s[a.se]==s[b.se]?s[a.fi]<s[b.fi]:s[a.se]<s[b.se];
	});
	for(auto[u,v]:EL){
		//pf("edge: %d %d\n",u,v);
		int pu=fp(u),pv=fp(v);
		if(pu==pv)continue;
		int p=join(pu,pv);
		if(tot[pu]>=s[v]){
			vi tmp;
			swap(ans[pu],tmp);
			if(sz(tmp)<sz(ans[pv]))swap(tmp,ans[pv]);
			for(int i:ans[pv])tmp.pb(i);
			swap(tmp,ans[p]);
		}
		else{
			if(pu==p)swap(ans[pu],ans[pv]);
		}
		tot[p]=tot[pu]+tot[pv];
		vector<int> clr;
		if(pu==p)swap(ans[pv],clr);
		else swap(ans[pu],clr);
		
		/*
		pf("now:\n");
		for(int i=0;i<n;++i){
			pf("%d %d: ",i,tot[i]);
			for(int x:ans[i])pf("%d ",x);
			pf("\n");
		}
		*/
	}
	int p=fp(0);
	for(int i:ans[p]){
		good[i]=true;
	}
	for(int i=0;i<n;++i)pf("%d",good[i]);
	pf("\n");
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:83:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  sf("%d%d",&n,&m);
      |    ^
island.cpp:85:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   sf("%d",&s[i]);
      |     ^
island.cpp:92:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   sf("%d%d",&a,&b);
      |     ^

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