QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121260#4839. Smaller LCAmemset0WA 3ms16048kbC++205.5kb2023-07-07 20:10:102023-07-07 20:10:12

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 20:10:12]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:16048kb
  • [2023-07-07 20:10:10]
  • 提交

answer

#include <bits/stdc++.h>
#include <time.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> cur, G[N];
vector<tuple<int, int, int, int>> qry;
struct CountNode {
  int n, tim, s[N << 2];
  vector<int> ans, val;
  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);
    val.push_back(x), val.push_back(y);
  }
  inline void addQuery(int x, int y) {
    // cerr << "counter::addQuery " << x << " " << y << endl;
    qry.emplace_back(x, y, qry.size());
    val.push_back(x), val.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(), val.clear();
  }
  void solve() {
    // cerr << "counter::solve" << endl;
    ans.resize(qry.size());
    fill(ans.begin(), ans.end(), 0);
    if (!nod.size()) return;
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    n = val.size();
    fill(s, s + n + 1, 0);
    for (auto &[x, y] : nod) {
      x = lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
      y = lower_bound(val.begin(), val.end(), y) - val.begin() + 1;
    }
    for (auto &[x, y, i] : qry) {
      x = lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
      y = lower_bound(val.begin(), val.end(), y) - val.begin() + 1;
    }
    sort(nod.begin(), nod.end());
    sort(qry.begin(), qry.end());
    int i = 0, j = 0;
    for (int x = 1; x <= n; 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) {
  // 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);
      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, int w) {
  int tot = getresult();
  // cerr << "push ans " << u << " " << w << " " << tot << endl;
  w += tot;
  ans[u] += w;
  for (int v : G[u])
    if (!vis[v] && v != fa[u]) {
      int sub = getresult();
      pushans(v, w - sub);
    }
}
void solve(int u) {
  // cerr << "=== solve " << u << " ===" << endl;
  vis[u] = 1;
  set<pair<int, int>> pre = {{u, 0}};
  map<int, vector<pair<int, int>>> p;
  tot = 1, dfn[u] = siz[u] = 1;
  for (int v : G[u])
    if (!vis[v]) {
      cur.clear();
      getnode(v);
      siz[u] += siz[v];
      p[v] = {};
      for (int x : cur) {
        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 : cur) pre.insert(make_pair(x, v));
    }
  qry.clear(), tim = 0;
  for (int v : G[u])
    if (!vis[v]) {
      getquery(v, v);
    }
  counter.init();
  for (const auto &[v, pv] : p)
    for (const auto &[x, y] : pv) {
      counter.addNode(dfn[x], 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 : G[u])
    if (!vis[v]) {
      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;
    }
  for (int v : G[u])
    if (!vis[v]) {
      pushans(v, 0);
    }
  for (int v : G[u])
    if (!vis[v]) {
      rt = 0, all = siz[v], getroot(v), solve(rt);
    }
}
int main() {
#ifdef memset0
  freopen("A2.in", "r", stdin);
#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]) << endl;
  cout << clock() / (double)CLOCKS_PER_SEC << endl;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 16048kb

input:

5
1 2
4 2
2 5
3 5

output:

15
15
15
15
14
0.003528

result:

wrong output format Expected integer, but "0.003528" found