oj.uz

Submission #640566

# Submission time Handle Problem Language Result Execution time Memory
640566 2022-09-15T00:49:41 Z kith14 Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 386592 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>

#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

const ll N = 2e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], vs[N];
ll x, y, k;
string s, s1, s2, ye = "YES", no = "NO";
vector<pairll> v;
vector<ll> ed[N];

void input(){
  cin >> n >> m;
  repp(i,1,n) cin >> ar[i];
  repp(i,1,m){
    cin >> x >> y;
    ed[x].pb(y);
    ed[y].pb(x);
  }
}

void sub1(){
  repp(i,1,n){
    ll cur = ar[i], vst = 1;
    priority_queue<pairll, vector<pairll>, greater<pairll> > pq;
    queue<ll> q;
    q.push(i);
    vs[i] = i;
    while(q.size()){
      ll a = q.front();
      //cout << i << " " << a << endl;
      q.pop();
      for (auto nx : ed[a]){
        if (vs[nx] == i) continue;
        if (ar[nx] > cur){
          pq.push(mp(ar[nx],nx));
        }
        else{
          cur += ar[nx];
          vs[nx] = i;
          q.push(nx);
          vst++;
        }
      }
      while(pq.size() && pq.top().fr <= cur){
        pairll a = pq.top();
        pq.pop();
        cur += a.fr;
        vs[a.sc] = i;
        q.push(a.sc);
        vst++;
      }
    } 
    cout << (vst == n); 
  }
}

ll sub[N], pos[N];
void dfs(ll idx, ll par){
  sub[idx] = ar[idx];
  for (auto i : ed[idx]){
    if (i == par) continue;
    dfs(i,idx);
    sub[idx] += sub[i];
  }
}

void ser(ll idx, ll par){
  for (auto i : ed[idx]){
    if (i == par) continue;
    if (sub[i] >= ar[idx]){
      pos[i] = 1;
      ser(i,idx);
    }
  }
}

void sub2(){
  //root is at 1
  dfs(1,-1);
  pos[1] = 1;
  ser(1,-1);
  repp(i,1,n) cout << pos[i];
  cout << endl;
}

void solve(){
  if (n <= 2e3 && m <= 2e3) sub1();
  else sub2();
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 53 ms 5076 KB Output is correct
5 Correct 53 ms 5152 KB Output is correct
6 Correct 71 ms 5148 KB Output is correct
7 Correct 50 ms 5076 KB Output is correct
8 Correct 37 ms 5076 KB Output is correct
9 Correct 52 ms 5076 KB Output is correct
10 Correct 46 ms 5076 KB Output is correct
11 Correct 45 ms 5140 KB Output is correct
12 Correct 31 ms 5192 KB Output is correct
13 Correct 80 ms 5132 KB Output is correct
14 Correct 28 ms 5196 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 3 ms 5028 KB Output is correct
3 Correct 142 ms 22388 KB Output is correct
4 Correct 128 ms 22704 KB Output is correct
5 Correct 177 ms 18732 KB Output is correct
6 Correct 158 ms 19248 KB Output is correct
7 Correct 174 ms 19224 KB Output is correct
8 Correct 183 ms 19576 KB Output is correct
9 Correct 136 ms 19728 KB Output is correct
10 Correct 99 ms 18176 KB Output is correct
11 Correct 95 ms 19816 KB Output is correct
12 Correct 145 ms 17844 KB Output is correct
13 Correct 130 ms 29064 KB Output is correct
14 Correct 115 ms 29248 KB Output is correct
15 Correct 151 ms 30932 KB Output is correct
16 Correct 88 ms 30324 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 128 ms 28812 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 5020 KB Output is correct
2 Execution timed out 1083 ms 386592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 53 ms 5076 KB Output is correct
5 Correct 53 ms 5152 KB Output is correct
6 Correct 71 ms 5148 KB Output is correct
7 Correct 50 ms 5076 KB Output is correct
8 Correct 37 ms 5076 KB Output is correct
9 Correct 52 ms 5076 KB Output is correct
10 Correct 46 ms 5076 KB Output is correct
11 Correct 45 ms 5140 KB Output is correct
12 Correct 31 ms 5192 KB Output is correct
13 Correct 80 ms 5132 KB Output is correct
14 Correct 28 ms 5196 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5028 KB Output is correct
17 Correct 142 ms 22388 KB Output is correct
18 Correct 128 ms 22704 KB Output is correct
19 Correct 177 ms 18732 KB Output is correct
20 Correct 158 ms 19248 KB Output is correct
21 Correct 174 ms 19224 KB Output is correct
22 Correct 183 ms 19576 KB Output is correct
23 Correct 136 ms 19728 KB Output is correct
24 Correct 99 ms 18176 KB Output is correct
25 Correct 95 ms 19816 KB Output is correct
26 Correct 145 ms 17844 KB Output is correct
27 Correct 130 ms 29064 KB Output is correct
28 Correct 115 ms 29248 KB Output is correct
29 Correct 151 ms 30932 KB Output is correct
30 Correct 88 ms 30324 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Incorrect 128 ms 28812 KB Output isn't correct
33 Halted 0 ms 0 KB -