제출 #1235187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235187		LucaIlie	Tree (IOI24_tree)	C++20	100 / 100	123 ms	23844 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
int n;
int parent[MAX_N], w[MAX_N], perm[MAX_N];
int sef[MAX_N], leaves[MAX_N], minW[MAX_N];
long long coefL[MAX_N + 1], coefR[MAX_N + 1];
vector<int> adj[MAX_N];

int findSef(int v) {
  if (sef[v] != v)
    sef[v] = findSef(sef[v]);
  return sef[v];
}

void init(vector<int> P, vector<int> W) {
  n = (int)W.size();
  for (int v = 0; v < n; v++) {
    parent[v] = P[v];
    if (v != 0)
      adj[parent[v]].push_back(v);
    w[v] = W[v];
  }

  for (int i = 0; i < n; i++)
    perm[i] = i;
  sort(perm, perm + n, [](int u, int v) { return w[u] < w[v]; });

  for (int v = 0; v < n; v++) {
    sef[v] = v;
    leaves[v] = 1;
    minW[v] = w[v];
  }

  for (int i = n - 1; i >= 0; i--) {
    int u = perm[i];
    if (adj[u].empty()) {
      coefL[n] += w[u];
      continue;
    }

    int a = findSef(u);
    coefL[leaves[a]] += (long long)(minW[a] - w[u]) * leaves[a];
    coefR[leaves[a]] -= minW[a] - w[u];
    for (int v: adj[u]) {
      int b = findSef(v);
      sef[b] = a;
      leaves[a] += leaves[b];
      //printf("%d %d %d %d %d\n", u, b, leaves[b], minW[b], w[u]);
      coefL[leaves[b]] += (long long)(minW[b] - w[u]) * leaves[b];
      coefR[leaves[b]] -= minW[b] - w[u];
    }
    minW[a] = w[u];
    leaves[a]--;
  }
  coefL[leaves[0]] += (long long)minW[0] * leaves[0];
  coefR[leaves[0]] -= minW[0];
  int b = findSef(0);
  //printf("%d %d %d\n", b, leaves[b], minW[b]);

  for (int i = n - 1; i >= 0; i--) {
    coefL[i] += coefL[i + 1];
    coefR[i] += coefR[i + 1];
  }

  //for (int i = 0; i <= n; i++)
   // printf("%lld %lld\n", coefL[i], coefR[i]);
}

long long query(int l, int r) {
  int k = min(n, r / l + 1);
  return l * coefL[k] + r * coefR[k];
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19