제출 #654460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654460		cadmiumsky	Stranded Far From Home (BOI22_island)	C++14	10 / 100	321 ms	32344 KiB

island

#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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35