oj.uz

Submission #654460

# Submission time Handle Problem Language Result Execution time Memory
654460 2022-10-31T11:11:26 Z cadmiumsky Stranded Far From Home (BOI22_island) C++14
10 / 100
 321 ms 32344 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
const ll inf = 1e18 + 5, nmax = 2e5 + 5;

//#define int ll
//#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

int rez[nmax];

namespace Tree {
  struct Node {
    ll limit; int value, id; ll area = 0; int sz = 0;
    Node(int i, int here): limit(inf), value(here), id(i), area(here), sz(1) {;}
  };
  int root;
  vector<Node> atr;
  vector<vector<int>> g;
  void addnew(int area, int val = -1) {
    root = atr.size();
    atr.emplace_back(val, area);
    g.emplace_back();
  }
  
  void addedge(int a, int b) {
    g[a].push_back(b);
    
  }
  
  void initdfs(int node = root) {
    for(auto x : g[node]) {
      initdfs(x);
      atr[node].area += atr[x].area;
      atr[node].sz += atr[x].sz;
    }
    return;
  }
  void dfs(int node = root, int highest = atr[root].sz) {
    if(atr[node].area < atr[node].limit)
      highest = atr[node].sz;
    //cerr << node << ' ' << highest << '\n';
    if(atr[node].id != -1)
      rez[atr[node].id] = highest;
    for(auto x : g[node]) {
      dfs(x, highest);
    }
  }
  
}

using namespace Tree;
int cost[nmax];
vector<tii> edg;

signed main() {
  int n, m;
  cin >> n >> m;
  for(int i = 0; i < n; i++) {
    cin >> cost[i];
    addnew(cost[i], i);
  }
  
  root = 0;
  assert(m == n - 1);
  for(int x, y, j = 0; j < m; j++) {
    cin >> x >> y;
    --x;
    --y;
    if(x > y)
      swap(x, y);
    addedge(x, y);
    atr[y].limit = cost[x];
  }
  initdfs();
  dfs();
  for(int i = 0; i < n; i++) {
    cout << (rez[i] == n);
  }
  cout << '\n';
}

/**
      Când iar începe-a ninge
      Mă simt de-un dor cuprins.
      Mă văd, pe-un drum, departe,
      Mergând, încet, şi nins.

      Sub streşină, cerdacul
      Se-ntunecă mâhnit;
      Stă rezimată-o fată
      De stâlpu-nzăpezit.
-- George Bacovia, Ninge
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 293 ms 21332 KB Output is correct
4 Correct 244 ms 24140 KB Output is correct
5 Correct 313 ms 20188 KB Output is correct
6 Correct 321 ms 20512 KB Output is correct
7 Correct 303 ms 20540 KB Output is correct
8 Correct 308 ms 20552 KB Output is correct
9 Correct 276 ms 19692 KB Output is correct
10 Correct 201 ms 18400 KB Output is correct
11 Correct 204 ms 18240 KB Output is correct
12 Correct 256 ms 20064 KB Output is correct
13 Correct 256 ms 31536 KB Output is correct
14 Correct 264 ms 31716 KB Output is correct
15 Correct 304 ms 32344 KB Output is correct
16 Correct 198 ms 31948 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 292 ms 28648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -