QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121308#4839. Smaller LCAmemset0Compile Error//C++206.7kb2023-07-07 21:55:382023-07-07 21:55:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 21:55:39]
  • 评测
  • [2023-07-07 21:55:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
int n, rt, all, tot, tim, fa[N], siz[N], mxp[N], dfn[N], ans[N];
bool vis[N];
vector<int> G[N];
vector<tuple<int, int, int, int>> qry;
namespace ini {
int tot, fa[N], dfn[N], siz[N];
long long sum, pre[N];
void dfs(int u) {
  dfn[u] = ++tot;
  for (int v : G[u])
    if (v != fa[u]) {
      fa[v] = u;
      dfs(v);
    }
}
void push(int u, int x) {
  pre[dfn[u]] += x;
  pre[dfn[u] + 1] -= x;
}
void push(int u, int v, int x) {
  if (v == fa[u]) {
    pre[0] += x;
    pre[dfn[u]] -= x;
    pre[dfn[u] + siz[u]] += x;
  } else {
    pre[dfn[v]] += x;
    pre[dfn[v] + siz[v]] -= -x;
  }
}
void init() { dfs(1); }
void solve() {
  for (int i = 1; i <= n; i++) pre[i] += pre[i - 1];
  for (int i = 1; i <= n; i++) ans[i] += pre[dfn[i]];
}
} // namespace ini
struct CountNode {
  int n, tim, s[N << 1];
  vector<int> ans, valx, valy;
  vector<pair<int, int>> nod;
  vector<tuple<int, int, int>> qry;
  inline void add(int k) {
    for (; k <= n; k += k & -k) s[k]++;
  }
  inline void ask(int k, int &x) {
    for (; k; k -= k & -k) x += s[k];
  }
  inline void addNode(int x, int y) {
    // cerr << "counter::addNode " << x << " " << y << endl;
    nod.emplace_back(x, y);
    valx.push_back(x), valy.push_back(y);
  }
  inline void addQuery(int x, int y) {
    // cerr << "counter::addQuery " << x << " " << y << endl;
    qry.emplace_back(x, y, qry.size());
    valx.push_back(x), valy.push_back(y);
  }
  inline int getQuery() {
    // cerr << "counter::getQuery " << ans[tim] << endl;
    return ans[tim++];
  }
  void init() {
    // cerr << "counter::init" << endl;
    tim = 0, nod.clear(), qry.clear(), valx.clear(), valy.clear();
  }
  void solve() {
    // cerr << "counter::solve" << endl;
    ans.resize(qry.size());
    fill(ans.begin(), ans.end(), 0);
    if (!nod.size()) return;
    sort(valx.begin(), valx.end());
    sort(valy.begin(), valy.end());
    valx.erase(unique(valx.begin(), valx.end()), valx.end());
    valy.erase(unique(valy.begin(), valy.end()), valy.end());
    n = valy.size();
    fill(s, s + n + 1, 0);
    for (auto &[x, y] : nod) {
      x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
      y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
    }
    for (auto &[x, y, i] : qry) {
      x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
      y = lower_bound(valy.begin(), valy.end(), y) - valy.begin() + 1;
    }
    sort(nod.begin(), nod.end());
    sort(qry.begin(), qry.end());
    int i = 0, j = 0;
    for (int x = 1; x <= valx.size(); x++) {
      while (i < nod.size() && nod[i].first == x) {
        add(nod[i].second), i++;
      }
      while (j < qry.size() && get<0>(qry[j]) == x) {
        ask(get<1>(qry[j]), ans[get<2>(qry[j])]), j++;
      }
    }
  }
} counter;
void getroot(int u) {
  siz[u] = 1;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      fa[v] = u;
      getroot(v);
      siz[u] += siz[v];
      mxp[u] = max(mxp[u], siz[v]);
    }
  mxp[u] = max(mxp[u], all - siz[u]);
  if (!rt || mxp[u] < mxp[rt]) rt = u;
}
void getnode(int u, vector<int> &cur) {
  // cerr << "get node " << u << endl;
  cur.push_back(u);
  dfn[u] = ++tot, siz[u] = 1;
  for (int v : G[u]) {
    if (!vis[v] && v != fa[u]) {
      fa[v] = u;
      getnode(v, cur);
      siz[u] += siz[v];
    }
  }
}
void getquery(int u, int sub) {
  // cerr << "get query " << u << endl;
  // qry.emplace_back(dfn[u] + siz[u] - 1, u - 1, sub, 0); // plus this ans
  // qry.emplace_back(dfn[u] - 1, u - 1, sub, 0);          // minus this ans
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      qry.emplace_back(dfn[v] + siz[v] - 1, u - 1, sub, 0); // plus this ans
      qry.emplace_back(dfn[v] - 1, u - 1, sub, 0);          // minus this ans
      getquery(v, sub);
    }
}
inline int getresult() {
  int res = get<3>(qry[tim++]);
  res -= get<3>(qry[tim++]);
  return res;
}
void pushans(int u) {
  // cerr << "push ans " << u << " " << w << " " << tot << endl;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      int cur = getresult();
      ini::pre[0] += cur;
      ini::push(u, -cur);
      ini::push(u, v, -cur);
      ini::push(u, fa[u], -cur);
      pushans(v);
    }
}
void solve(int u) {
  cerr << "=== solve " << u << " ===" << endl;
  vis[u] = 1;
  vector<int> ch;
  set<pair<int, int>> pre = {{u, 0}};
  map<int, vector<int>> d;
  map<int, vector<pair<int, int>>> p;
  p[0] = {};
  tot = 1, dfn[u] = siz[u] = 1;
  for (int v : G[u]) {
    if (!vis[v]) ch.push_back(v);
  }
  for (int v : ch) {
    fa[v] = u;
    d[v] = {};
    getnode(v, d[v]);
    siz[u] += siz[v];
    p[v] = {};
    for (int x : d[v])
      for (auto &[y, w] : pre) {
        if ((long long)x * y < n) {
          p[w].emplace_back(y, x);
          p[v].emplace_back(x, y);
        } else {
          break;
        }
      }
    for (int x : d[v]) pre.insert(make_pair(x, v));
  }
  qry.clear(), tim = 0;
  for (int v : ch) getquery(v, v);
  counter.init();
  for (const auto &[v, pv] : p)
    for (const auto &[x, y] : pv) {
      counter.addNode(dfn[x], x * y);
      // cerr << "find " << x << " " << y << endl;
      if (x < y && u > (long long)x * y) {
        
      }
    }
  for (auto &[x, y, v, ans] : qry) {
    counter.addQuery(x, y);
  }
  counter.solve();
  for (auto &[x, y, v, ans] : qry) {
    ans += counter.getQuery();
  }
  int i = 0, j;
  for (int v : ch) {
    counter.init(), j = i;
    while (j < qry.size() && get<2>(qry[j]) == v) {
      counter.addQuery(get<0>(qry[j]), get<1>(qry[j])), j++;
    }
    counter.solve(), j = i;
    while (j < qry.size() && get<2>(qry[j]) == v) {
      get<3>(qry[j]) -= counter.getQuery(), j++;
    }
    i = j + 1;
  }
  ans[u] += curans;
  for (int v : ch) {
    int subans = 0;
    ini::push(u, v, curans);
    for (auto &[x, y] : p[v])
      if (u > (long long)x * y) subans++;
    pushans(v, curans - subans);
  }
  for (int v : ch) {
    rt = 0, all = siz[v], getroot(v), solve(rt);
  }
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
  // freopen("2.in", "r", stdin);
  // freopen("2.out", "w", stdout);
#endif
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int u, v, i = 1; i < n; i++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  rt = 0, all = n, getroot(1), solve(rt);
  long long tot = (long long)n * (n - 1) / 2 + n;
  for (int i = 1; i <= n; i++) cerr << ans[i] << " \n"[i == n];
  for (int i = 1; i <= n; i++) cout << (tot - ans[i]) << '\n';
  cerr << "time: " << clock() / (double)CLOCKS_PER_SEC << endl;
}

Details

answer.code: In function ‘void solve(int)’:
answer.code:211:13: error: ‘curans’ was not declared in this scope; did you mean ‘wctrans’?
  211 |   ans[u] += curans;
      |             ^~~~~~
      |             wctrans