Submission #1121544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121544		vjudge1	Stranded Far From Home (BOI22_island)	C++17	0 / 100	235 ms	44988 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], id[maxn], sz, p[maxn];
ll a[maxn], sum[maxn];
vector <int> g[maxn], gr[maxn], cmp, tp;
vector <pair <int, int> > g2[maxn];

void topsort(int v) {
	used[v] = 1;
	for (auto to: g[v]) {
		if (used[to] == 0) {
			topsort(to);
		}
	}
	tp.pb(v);
}

void dfs(int v) {
	used[v] = 1;
	cmp.pb(v);
	for (auto to: gr[v]) {
		if (used[to] == 0) {
			dfs(to);
		}
	}
}


void dfs2(int v) {
	used[v] = 1;
	for (auto to: g2[v]) {
		if (used[to.ff] == 0) {
			dfs2(to.ff);
		}
	}
	tp.pb(v);
}

int get(int v) {
	if (v == p[v]) {
		return v;
	}
	p[v] = get(p[v]);
	return p[v];
}

void merge(int v, int u) {
	int pv = get(v);
	int pu = get(u);
	if (pv != pu) {
		p[pu] = pv;
	}
}

void press_F_() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		merge(x, y);
		if (a[x] >= a[y]) {
			g[x].pb(y);
			gr[y].pb(x);
		}
		if (a[y] >= a[x]) {
			g[y].pb(x);
			gr[x].pb(y);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (used[i] == 0) {
			topsort(i);
		}
	}
	reverse(tp.begin(), tp.end());
	for (int i = 1; i <= n; i++) {
		used[i] = 0;
		if (get(1) != get(i)) {
			for (int j = 1; j <= n; j++) {
				cout << 0;
			}
			return;
		}
	}
	for (auto v: tp) {
		if (used[v] == 0) {
			cmp.clear();
			dfs(v);
			sz++;
			ok[sz] = 1;
			for (auto to: cmp) {
				id[to] = sz;
				sum[sz] += a[to];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		used[i] = 0;
		for (auto to: g[i]) {
			if (id[i] != id[to]) {
				g2[id[i]].pb({id[to], a[i]});
			}
		}
	}
	tp.clear();
	for (int i = 1; i <= sz; i++) {
		if (used[i] == 0) {
			dfs2(i);
		}
	}
	for (auto v: tp) {
		for (auto to: g2[v]) {
			if (sum[to.ff] < to.ss) {
				ok[to.ff] = 0;
			}
			sum[v] += sum[to.ff];
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << ok[id[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