Submission #798789

#	Time	Username	Problem	Language	Result	Execution time	Memory
798789		NeroZein	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	323 ms	79804 KiB

railroad

#include "bits/stdc++.h"
#include "railroad.h"

using namespace std;

const int N = 2e5 + 5; 

int n;
bool leaf[N * 2];
vector<int> g[N * 2];
vector<int> rg[N * 2];
int id_in_tree[N];

void add_edge (int u, int v) {
  g[u].push_back(v);
  rg[v].push_back(u);
}

void build (int nd, int l, int r) {
  if (l == r) {
    id_in_tree[l] = nd;
    leaf[nd] = true;
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  add_edge(nd, nd + 1);
  add_edge(nd, rs); 
  build(nd + 1, l, mid);
  build(rs, mid + 1, r); 
}

void add (int nd, int l, int r, int s, int e, int x) {
  if (l >= s && r <= e) {
    add_edge(x, nd); 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return add(nd + 1, l, mid, s, e, x);
  } else {
    if (mid < s) {
      return add(rs, mid + 1, r, s, e, x);
    }
    add(nd + 1, l, mid, s, e, x);
    add(rs, mid + 1, r, s, e, x); 
  }
}

void add (int l, int r, int x) {
  if (l > r) return;
  add(0, 0, n - 1, l, r, x); 
}

int vis[N * 2]; 
vector<int> stk;
void dfs (int v) {
  vis[v] = 1;
  for (int u : g[v]) {
    if (!vis[u]) {
      dfs(u); 
    }
  }
  stk.push_back(v);
}

int dp[N * 2]; 

void dfs2 (int v, int ncc, vector<int>& comp) {
  comp.push_back(v);
  vis[v] = ncc;
  for (int u : rg[v]) {
    if (vis[u] == -1) {
      dfs2(u, ncc, comp);
    } 
  }
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  n = (int) s.size();
  vector<array<int, 3>> arr(n);
  for (int i = 0; i < n; ++i) {
    arr[i] = {s[i], t[i], i};
  }
  sort(arr.begin(), arr.end()); 
  build(0, 0, n - 1); 
  for (int i = 0; i < n; ++i) {
    array<int, 3> key = {arr[i][1], -1, -1};
    int first_with_bigger_s = lower_bound(arr.begin(), arr.end(), key) - arr.begin();
    add(first_with_bigger_s, n - 1, id_in_tree[i]); 
  }
  for (int i = 0; i < id_in_tree[n - 1]; ++i) {
    if (!vis[i]) {
      dfs(i);
    }
  }
  //cout << "STK: ";
  //for (int i : stk) {
    //cout << i << ' ';
  //}
  //cout << '\n';
  int ncc = 0; 
  int longest_path = 1;
  fill(vis, vis + N * 2, -1); 
  for (int i = (int) stk.size() - 1; i >= 0; --i) {
    if (vis[stk[i]] == -1) {
      vector<int> comp;
      dfs2(stk[i], ncc, comp);
      for (int v : comp) {
        for (int u : rg[v]) {
          if (vis[u] != ncc) {
            dp[ncc] = max(dp[ncc], dp[vis[u]]);            
          }
        }
      }
      //cout << "COMP: ";
      for (int v : comp) {
        //cout << v << ' ';
        dp[ncc] += leaf[v]; 
      }
      //cout << '\n';
      //cout << "DP: " << dp[ncc] << '\n' << '\n';
      longest_path = max(longest_path, dp[ncc]); 
      ncc++;
    }
  }
  //cout << "LONGEST: " << longest_path << '\n';
  return (longest_path == n);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36