oj.uz

Submission #640278

# Submission time Handle Problem Language Result Execution time Memory
640278 2022-09-14T05:31:48 Z andecaandeci Stranded Far From Home (BOI22_island) C++17
20 / 100
 212 ms 24120 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 157 ms 5080 KB Output is correct
5 Correct 144 ms 5088 KB Output is correct
6 Correct 212 ms 5076 KB Output is correct
7 Correct 159 ms 5076 KB Output is correct
8 Correct 102 ms 5076 KB Output is correct
9 Correct 204 ms 5104 KB Output is correct
10 Correct 64 ms 5076 KB Output is correct
11 Correct 63 ms 5084 KB Output is correct
12 Correct 60 ms 5076 KB Output is correct
13 Correct 113 ms 5196 KB Output is correct
14 Correct 85 ms 5080 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5064 KB Output is correct
3 Correct 101 ms 16472 KB Output is correct
4 Correct 93 ms 16376 KB Output is correct
5 Correct 121 ms 12284 KB Output is correct
6 Correct 112 ms 12412 KB Output is correct
7 Correct 114 ms 12512 KB Output is correct
8 Correct 114 ms 12540 KB Output is correct
9 Correct 94 ms 11516 KB Output is correct
10 Correct 60 ms 9168 KB Output is correct
11 Correct 60 ms 9356 KB Output is correct
12 Correct 101 ms 12288 KB Output is correct
13 Correct 106 ms 23876 KB Output is correct
14 Correct 98 ms 23936 KB Output is correct
15 Correct 107 ms 24120 KB Output is correct
16 Correct 74 ms 23880 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 96 ms 12744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 93 ms 10424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 157 ms 5080 KB Output is correct
5 Correct 144 ms 5088 KB Output is correct
6 Correct 212 ms 5076 KB Output is correct
7 Correct 159 ms 5076 KB Output is correct
8 Correct 102 ms 5076 KB Output is correct
9 Correct 204 ms 5104 KB Output is correct
10 Correct 64 ms 5076 KB Output is correct
11 Correct 63 ms 5084 KB Output is correct
12 Correct 60 ms 5076 KB Output is correct
13 Correct 113 ms 5196 KB Output is correct
14 Correct 85 ms 5080 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 5064 KB Output is correct
17 Correct 101 ms 16472 KB Output is correct
18 Correct 93 ms 16376 KB Output is correct
19 Correct 121 ms 12284 KB Output is correct
20 Correct 112 ms 12412 KB Output is correct
21 Correct 114 ms 12512 KB Output is correct
22 Correct 114 ms 12540 KB Output is correct
23 Correct 94 ms 11516 KB Output is correct
24 Correct 60 ms 9168 KB Output is correct
25 Correct 60 ms 9356 KB Output is correct
26 Correct 101 ms 12288 KB Output is correct
27 Correct 106 ms 23876 KB Output is correct
28 Correct 98 ms 23936 KB Output is correct
29 Correct 107 ms 24120 KB Output is correct
30 Correct 74 ms 23880 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Incorrect 96 ms 12744 KB Output isn't correct
33 Halted 0 ms 0 KB -