Submission #1121660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121660		vjudge1	Stranded Far From Home (BOI22_island)	C++17	0 / 100	227 ms	38096 KiB

island

//Bismillahir-Rahmanir-Rahim
#include <bits/stdc++.h>
 
using namespace std;
 
#define flash ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long
#define ld long double
#define dbg(x) cerr << #x << " = " << x << "\n";
#define ff first
#define ss second
#define y1 lol
 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma comment (linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
 
const long long INF = 1e9 + 7;
const long long MOD = 1e9 + 7;
const int maxn = 2e5 + 10;
const int lg = 30;

int n, m, used[maxn], ok[maxn];
vector <pair <int, int> > g[maxn];
vector <int> gr[maxn];
ll a[maxn], sum[maxn], sumall;
vector <int> tp;
vector <pair <int, int> > ls;
	
void dfs(int v, int p) {
	used[v] = 1;
	tp.pb(v);
	for (auto to: g[v]) {
		if (used[to.ss] == 0 && to.ff <= sumall) {
			gr[to.ss].pb(p);
			if (a[to.ss] >= a[v]) {
				gr[p].pb(to.ss);
			}
			sumall += sum[to.ss];
			dfs(to.ss, p);
		}
		if (used[to.ss] == 1 && sum[to.ss] < a[v]) {
			sumall += sum[to.ss];
			gr[to.ss].pb(v);
		}
	}
}
	
void color(int v) {
	ok[v] = 1;
	for (auto to: gr[v]) {
		if (ok[to] == 0) {
			ok[to] = 1;
			color(to);
		}
	}
}
	
void press_F_() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = a[i];
		ls.pb({a[i], i});
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].pb({a[y], y});
		g[y].pb({a[x], x});
	}
	for (int i = 1; i <= n; i++) {
		sort(g[i].begin(), g[i].end());
	}
	sort(ls.begin(), ls.end());
	for (int i = 0; i < n; i++) {
		sumall = sum[ls[i].ss];
		tp.clear();
		dfs(ls[i].ss, ls[i].ss);
		for (auto to: tp) {
			sum[to] = sumall;
		}
	}
	color(ls[n - 1].ss);
	for (int i = 1; i <= n; i++) {
		cout << ok[i];
	}
}
 
int main() {
    flash;
    int T = 1;
    // cin >> T;
    for (int _ = 1; _ <= T; ++_) {
        // cout << "Case " << i << ": ";
        press_F_();
		
    }
    //Respa gold 2025 InshAllah
    // return 0;
}
/*
Maybe not today and tomorrow, but InshAllah one day I will reach cm
*/
// g++ -std=c++17 main.cpp
// ./a.out

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