제출 #1210454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210454		trimkus	트리 (IOI24_tree)	C++20	0 / 100	2097 ms	24000 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2000;
int N;
vector<int> W;
vector<vector<int>> adj;
int tin[MAXN], tout[MAXN], depth[MAXN];
struct Fenwick {
  int n;
  vector<int> bit;
  Fenwick(int n) {
    this->n = n;
    bit = vector<int>(n + 1);
  }
  void update(int i, int delta) {
    for (i += 1; i <= n; i += i & -i) {
      bit[i] += delta;
    }
  }
  int sum(int i) {
    int res = 0;
    for (i += 1; i > 0; i -= i & -i) {
      res += bit[i];
    }
    return res;
  }
  int sum(int l, int r) {
    return sum(r) - sum(l - 1);
  }
  void init() {
    for (int i = 0; i <= n; ++i) {
      bit[i] = 0;
    }
  }
} tree(MAXN * 2);
void init(std::vector<int> P, std::vector<int> _W) {
  N = (int)P.size();
  W = _W;
  adj.resize(N);
  for (int i = 1; i < N; ++i) {
      adj[P[i]].push_back(i);
      adj[i].push_back(P[i]);
  }
  vector<vector<int>> nadj(N);
  vector<bool> vis(N);
  for (int i = 1; i < N; ++i) {
    if (vis[i]) continue;
    if (adj[i].size() == 2) {
      int v1 = adj[i][0];
      int v2 = adj[i][1];
      int p1 = i;
      int p2 = i;
      vis[i] = 1;
      while (adj[v1].size() == 2 && v1 != 0) {
        vis[v1] = 1;
        for (auto& u : adj[v1]) {
          if (u != p1) {
            p1 = v1;
            v1 = u;
            break;
          }
        }
      }
      while (adj[v2].size() == 2 && v2 != 0) {
        vis[v2] = 1;
        for (auto& u : adj[v2]) {
          if (u != p2) {
            p1 = v2;
            v2 = u;
            break;
          }
        }
      }
      cerr << "Found new = " << v1 << " " << v2 << "\n";
      nadj[v1].push_back(v2);
      nadj[v2].push_back(v1);
    } else {
      for (auto& u : adj[i]) {
        if (u != 0 && adj[u].size() == 2) continue;
        nadj[u].push_back(i);
        nadj[i].push_back(u);
      }
    }
  }
  adj = nadj;
  for (auto& v : adj) {sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v));}
  int t = 1;
  cerr << "Size = " << adj.size() << endl;
  for (int i = 0; i < N; ++i) {
    cerr << i << " : ";
    for (auto& u : adj[i]) {
      cout << u << " , ";
    }
    cout << endl;
  }
  auto dfs = [&](auto& dfs, int v, int p) -> void {
    tin[v] = t++;
    for (auto& u : adj[v]) {
      if (u == p) continue;
      cout << "Vertices " << v << " and " << u << " are connected!\n";
      depth[u] = depth[v] + 1;
      dfs(dfs, u, v);

    }  
    tout[v] = t++;
  };
  dfs(dfs, 0, -1);
}

long long query(int L, int R) {
  // cerr << "QUERY WITH " << L << " " << R << endl;
  ll res = 0;
  queue<int> q;
  tree.init();
  for (int i = 1; i < N; ++i) {
    if (adj[i].size() == 1) {
      res += 1LL * W[i] * L;
      q.push(adj[i][0]);
      tree.update(tin[i], +L);
    }
  }
  vector<bool> inq(N);
  vector<priority_queue<pair<int, int>>> leaves(N);
  while (q.size()) {
    int v = q.front();
    q.pop();
    int sum = tree.sum(tin[v], tout[v]);
    leaves[v].push({-W[v], v});
    while (leaves[v].size() && sum < L) {
      int current = leaves[v].top().second;
      leaves[v].pop();
      int left = L - sum;
      res += left * W[current];
      tree.update(tin[current], +left);
      sum += left;
      leaves[v].push({-W[current], current});
    }
    while (leaves[v].size() && sum > R) {
      int current = leaves[v].top().second;
      leaves[v].pop();
      int left = min(sum - R, max(0, tree.sum(tin[current], tout[current]) - L));
      if (left == 0) continue;
      res += left * W[current];
      tree.update(tin[current], -left);
      sum -= left;
      leaves[v].push({-W[current], current});
    }
    for (auto& u : adj[v]) {
      if (depth[u] < depth[v]) {
        while (leaves[v].size()) {
          auto top = leaves[v].top();
          leaves[v].pop();
          leaves[u].push(top);
        }
        if (!inq[u]) {
          q.push(u);
          inq[u] = 1;
        }
      }
    }
  }
  return res;
}

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