Submission #654463

#	Time	Username	Problem	Language	Result	Execution time	Memory
654463		cadmiumsky	Stranded Far From Home (BOI22_island)	C++14	100 / 100	426 ms	47340 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, int dim): limit(inf), value(here), id(i), area(here), sz(dim) {;}
  };
  int root;
  vector<Node> atr;
  vector<vector<int>> g;
  int addnew(int area = 0, int val = -1, int dim = 0) {
    root = atr.size();
    atr.emplace_back(val, area, dim);
    g.emplace_back();
    return root;
  }
  
  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);
    }
  }
}

namespace DSU {
  int dsu[nmax * 2];
  void init(int n) {
    for(int i = 0; i < 2 * n; i++) {
      dsu[i] = i;
    }
  }
  int f(int x) { return (dsu[x] == x? x : f(dsu[x] = f(dsu[dsu[x]]))); }
  void unite(int cost, int a, int b) {
    //cerr << a << ' ' << b << ' ' << cost << '\n';
    a = f(a);
    b = f(b);
    if(a == b)
      return;
    int nv = Tree::addnew();
    dsu[a] = nv;
    dsu[b] = nv;
    Tree::addedge(nv, a);
    Tree::addedge(nv, b);
    Tree::atr[a].limit = cost;
    Tree::atr[b].limit = cost;
    //cerr << nv << '\n';
    
  }
}

//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];
    Tree::addnew(cost[i], i, 1);
  }
  
  //assert(m == n - 1);
  for(int x, y, j = 0; j < m; j++) {
    cin >> x >> y;
    --x;
    --y;
    edg.emplace_back(max(cost[x], cost[y]), x, y);
  }
  sort(all(edg));
  DSU::init(n);
  for(auto [cost, a, b] : edg) {
    DSU::unite(cost, a, b);
  }
  Tree::initdfs();
  Tree::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
*/

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:103:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |   for(auto [cost, a, b] : edg) {
      |            ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35