Submission #640278

#	Time	Username	Problem	Language	Result	Execution time	Memory
640278		andecaandeci	Stranded Far From Home (BOI22_island)	C++17	20 / 100	212 ms	24120 KiB

island

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=2e5+5;
const int INF=1e9+5;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, m, u, v, arr[maxn], par[maxn], nah=1;
ll cnt[maxn], pref[maxn], suf[maxn], cur;
vi adj[maxn];
bool ans[maxn], bs=1, vis[maxn];
void dfs(int now) {
    cnt[now]=arr[now];
    for(auto it : adj[now]) {
        dfs(it);
        cnt[now]+=cnt[it];
    }
}
int main() {
    ok
    cin >> n >> m;
    if(n==1) {
        cout << 1;
        return 0;
    }
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
        if(i>1 && arr[i-1]<arr[i]) bs=0;
    }
    if(n<=2000 && m<=2000) {
        for(int i=0; i<m; i++) {
            cin >> u >> v;
            adj[u].pb(v);
            adj[v].pb(u);
        }
        for(int i=1; i<=n; i++) {
            nah=1;
            priority_queue<pii, vector<pii>, greater<pii>> pq;
            cur=arr[i];
            vis[i]=1;
            for(auto it : adj[i]) {
                pq.push({arr[it], it});
                vis[it]=1;
            }
            while(!pq.empty()) {
                pii fr=pq.top();
                //cout << fr.se;
                pq.pop();
                if(cur>=fr.fi) {
                    nah++;
                    cur+=fr.fi;
                    for(auto it : adj[fr.se]) {
                        if(!vis[it]) {
                            vis[it]=1;
                            pq.push({arr[it], it});
                        }
                    }
                } else break;
            }
            //cout << endl;
            //cout << nah;
            if(nah==n) cout << 1;
            else cout << 0;
            for(int i=1; i<=n; i++) vis[i]=0;
        }
        return 0;
    }
    for(int i=0; i<m; i++) {
        cin >> u >> v;
        adj[min(u, v)].pb(max(u, v));
        par[max(u, v)]=min(u, v);
    }
    if(bs && m==n-1) {
        dfs(1);
        ans[1]=1;
        cout << 1;
        for(int i=2; i<=n; i++) {
            if(cnt[i]>=arr[par[i]] && ans[par[i]]) {
                ans[i]=1;
            }
            cout << ans[i];
        }
    }
    for(int i=1; i<=n; i++) {
        
    }
}

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