Submission #723300

#	Time	Username	Problem	Language	Result	Execution time	Memory
723300		MurotY	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1059 ms	216248 KiB

island

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz size()
using namespace std;
const double pi = 2 * acos(0.0);
const ll N=1e6+7, M=998244353;
vector <ll> g[N];
ll a[N], res[N];  
ll sum[N], ans[N];
ll dfs(int v, int p){
    sum[v]=a[v];
    for (auto l:g[v]){
        if (l != p){
            sum[v]+=dfs(l, v);
        }
    }
    return sum[v];
}

void dfs1(int v, int p){
    if(v == 1) ans[v] = 1;
    else{
        ans[v] = (sum[v] >= a[p]);
    }
    if(!ans[v]) return;
    for (auto l:g[v]){
        if (l != p){
            dfs1(l, v);
        }
    }
    return ;
}
void solve()
{
	int n, m;
	cin >> n >> m;
	
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=m;i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
    if (n <= 2000 && m <= 2000){
		for (int i=1;i<=n;i++){
			set <pair <ll, ll>> q;
			vector <int> u(n+5, 0);
			q.insert({0, i});
			ll sum=0, cnt=0;
			while (!q.empty()){
			    pair <ll,ll> mn=*q.begin();
			    if (sum < mn.ff) break;
			    if (u[mn.ss]) continue;
			    u[mn.ss]=1;
			    q.erase(mn);
			    sum+=a[mn.ss];
			    for (auto l:g[mn.ss]){
			        if (!u[l]) {
			            q.insert({a[l], l});
			        }
			    }
			}
			if (q.sz == 0) cout << "1";
			else cout << "0";
		}
		return ;
    }
    dfs(1, 1);
    dfs1(1, 1);
    for (int i=1;i<=n;i++) cout << ans[i] << " ";
    return;
}
int main(){
	ios;
	int t=1;	
//	cin >> t;
	while (t--){ 
	    solve();
	    cout << "\n";
	}
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:58:14: warning: unused variable 'cnt' [-Wunused-variable]
   58 |    ll sum=0, cnt=0;
      |              ^~~

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