Submission #580461

#	Time	Username	Problem	Language	Result	Execution time	Memory
580461		haojiandan	Stranded Far From Home (BOI22_island)	C++14	100 / 100	143 ms	33196 KiB

island

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=(4e5)+10;
int n,m;
ll s[maxn],t[maxn];
vector<int> g[maxn];
struct node {
	int x,y;
	friend bool operator < (node A,node B) { return s[A.x]<s[B.x]; }
} E[maxn];
int fa[maxn],f[maxn],tot;
int find(int x) {
	if (fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
bool mk[maxn];
char S[maxn];
void dfs(int u) {
	if (mk[u]) return;
	if (u<=n) S[u]='1';
	for (int &v : g[u]) dfs(v);
}
int main() {
	read(n),read(m);
	for (int i=1;i<=n;i++) read(s[i]),t[i]=s[i],f[i]=fa[i]=i;
	tot=n;
	int x,y;
	for (int i=1;i<=m;i++) {
		read(x),read(y);
		if (s[x]<s[y]) swap(x,y);
		E[i]=(node){x,y};
	}
	sort(E+1,E+m+1);
	for (int i=1;i<=m;i++) {
		x=E[i].x,y=E[i].y;
		if (find(x)==find(y)) continue;
		y=find(y);
		if (t[y]<s[x]) mk[f[y]]=1;
		x=find(x);
		fa[x]=y,t[y]+=t[x],tot++;
		g[tot].push_back(f[x]),g[tot].push_back(f[y]);
		f[x]=tot,f[y]=tot;
	}
	for (int i=1;i<=n;i++) S[i]='0';
	dfs(tot);
	printf("%s\n",S+1);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

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