oj.uz

Submission #601039

# Submission time Handle Problem Language Result Execution time Memory
601039 2022-07-21T10:24:19 Z TimDee Stranded Far From Home (BOI22_island) C++17
10 / 100
 415 ms 31584 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define paiu return
#define moment 0;
 
#define int long long
#define double long double
#define ll long long

#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)

#define vi(a,n) vector<int> a(n,0)
 
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
    int n=a.size();
    vi(pr,n+1);
    forn(i,n) pr[i+1]=pr[i]+a[i];
    return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);
 
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
 
#define f first
#define s second
 
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
 
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
     
const int maxn = 1e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;

vector<int> a;
auto cmp = [](int i, int j) { return a[i]<=a[j]; };

void solve() {
    
    int n,m; cin>>n>>m;
    vii(b,n); a=b;
    vector<vector<int>> adj(n);
    forn(i,m) {
        int u,v; cin>>u>>v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    string ans(n,'1');

    forn(i,n) {
        set<int,decltype(cmp)> s(cmp);
        int cnt=a[i];
        bitset<2000> vis; vis.set(i,1); //cout<<i+1<<"->";
        for (auto v:adj[i]) { s.insert(v); vis.set(v,1); }
        while (!s.empty()) {
            auto it=s.begin();
            int u=*it;
            //cout<<u+1<<"->";
            if (a[u]>cnt) {ans[i]='0'; break;}
            cnt+=a[u]; 
            vis.set(u,1);
            s.erase(it);
            for (auto v:adj[u]) if (!vis[v]) { s.insert(v); vis.set(v,1); }
        }
        //cout<<'\n';
    }
    cout<<ans;
    
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int t=1;
    //cin>>t;
    while(t--) solve();
    
    paiu moment
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 216 ms 468 KB Output is correct
5 Correct 227 ms 468 KB Output is correct
6 Correct 269 ms 448 KB Output is correct
7 Correct 193 ms 468 KB Output is correct
8 Correct 150 ms 432 KB Output is correct
9 Correct 415 ms 504 KB Output is correct
10 Correct 99 ms 468 KB Output is correct
11 Correct 116 ms 476 KB Output is correct
12 Correct 130 ms 508 KB Output is correct
13 Correct 174 ms 468 KB Output is correct
14 Correct 108 ms 472 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 114 ms 31584 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 119 ms 29292 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 140 ms 31428 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 216 ms 468 KB Output is correct
5 Correct 227 ms 468 KB Output is correct
6 Correct 269 ms 448 KB Output is correct
7 Correct 193 ms 468 KB Output is correct
8 Correct 150 ms 432 KB Output is correct
9 Correct 415 ms 504 KB Output is correct
10 Correct 99 ms 468 KB Output is correct
11 Correct 116 ms 476 KB Output is correct
12 Correct 130 ms 508 KB Output is correct
13 Correct 174 ms 468 KB Output is correct
14 Correct 108 ms 472 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Runtime error 114 ms 31584 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -