Submission #999730

#	Time	Username	Problem	Language	Result	Execution time	Memory
999730		vjudge1	Construction of Highway (JOI18_construction)	C++17	16 / 100	2055 ms	23748 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set =
    tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 100'010;
const int LG = 20;
int up[N][LG], depth[N], n, sz[N];
vector<int> g[N];
int c[N];
void dfs(int at, int p) {
  up[at][0] = p;
  sz[at]=1;
  for(int i = 1;i < LG;i++) {
    up[at][i] = up[up[at][i-1]][i-1];
  }
  for(int to:g[at]) {
    if(to == p)continue;
    depth[to] = depth[at]+1;
    dfs(to, at);
    sz[at]+=sz[to];
  }
}
int lca(int a, int b) {
  if(depth[a] < depth[b])swap(a, b);
  int k = depth[a] - depth[b];
  for(int i = LG-1;i>=0;i--) {
    if(k&(1<<i)) {
      a = up[a][i];
    }
  }
  if(a==b)return a;
  for(int i = LG-1;i>=0;i--) {
    if(up[a][i] != up[b][i]) {
      a=up[a][i];
      b=up[b][i];
    }
  }
  return up[a][0];
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for(int i = 1;i<=n;i++)cin >> c[i];
  vector<pair<int,int>> e;
  for(int i = 1;i<n;i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
    e.push_back({a, b});
  }
  dfs(1, 0);
  int cnt=0;
  for(auto [a, b]:e) {
    int ans = 0;
    ordered_set<int> s;
    int cur=a;
    int prev =0;
    do {
      ans+=s.order_of_key(c[cur]);
      if(c[cur] != prev) {
        cnt++;
        prev = c[cur];
      }
      s.insert(c[cur]);
      cur = up[cur][0];
    }while(cur!=0);
    cur=a;
    do {
      c[cur] = c[b];
      cur = up[cur][0];
    }while(cur!=0);
    cout << ans << "\n";
  }
  assert(cnt <= max(100, n*50));
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84