Submission #1017827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017827		ZeroCool	Stranded Far From Home (BOI22_island)	C++14	100 / 100	178 ms	16472 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

using ll = long long;
using ld = long double;
 
void solve(int T);
void pre();
 
const int N = 2e5 + 10;
const int M = 405;
const int SQRT = 500;
const int LOG = 20;
const int INF = 1e18;
const int MOD = 1e9+7;
const ld EPS = 1e-9;

void pre(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	
}

int32_t main(){
	pre();
	int tt = 1;
	//cin>>tt;
	for(int i = 1;i<=tt;i++){
		//cerr<<"Case "<<i<<": "<<endl;
		solve(i);
	}
    return 0;
}



struct Edge{
	int u,v,w;
	
};
bool operator<(Edge a,Edge b){
	return a.w < b.w;
}

bool bad[N];

int A[N];
int sum[N];

int p[N];

int find(int u){
	if(p[u] == u)return u;
	int v = find(p[u]);
	bad[u] |= bad[p[u]];
	p[u] = v;
	return v;
}

void join(int u,int v){
	u = find(u);
	v = find(v);

	if(u == v)return;
	if(A[u] < A[v])swap(u,v);
	if(A[u] > sum[v])bad[v] = true;
	p[v] = u;
	sum[u] += sum[v];
}

void solve(int T){
    int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		cin>>A[i];
		p[i] = i;
		sum[i] = A[i];
	}
	Edge edge[m];
	for(int i = 0;i<m;i++){
		int u,v;
		cin>>u>>v;
		edge[i] = {u, v, max(A[u], A[v])}; 
	}
	sort(edge, edge + m);

	for(auto p : edge){
		join(p.u, p.v);
	}
	cerr<<"kur"<<endl;


	for(int i = 1;i<=n;i++){
		find(i);
		cout<<!bad[i];
	}
	cout<<endl;
}

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