Submission #1142090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142090		byunjaewoo	Tree (IOI24_tree)	C++20	100 / 100	129 ms	40328 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int N=200010, M=1000010;
int n, p[N], g[N], a[N];
bool w[N];
vector<pair<int, int>> v;
ll x[N], y[N], l[N];
ll tot, c[M], s[M];
vector<int> adj[N];

int Find(int x) {return g[x]?(g[x]=Find(g[x])):x;}
void Union(int u, int v, ll t) {
  u=Find(u), v=Find(v);
  if(l[u]) tot+=x[u]*(l[u]-t), c[y[u]]+=(l[u]-t), s[y[u]]+=y[u]*(l[u]-t);
  if(l[v]) tot+=x[v]*(l[v]-t), c[y[v]]+=(l[v]-t), s[y[v]]+=y[v]*(l[v]-t);
  x[v]+=x[u], y[v]+=y[u], l[v]=t, g[u]=v;
}

void init(vector<int> P, vector<int> W) {
  n=P.size();
  for(int i=1; i<=n; i++) a[i]=W[i-1], v.push_back({a[i], i});
  for(int i=2; i<=n; i++) p[i]=P[i-1]+1, adj[p[i]].push_back(i);
  for(int i=1; i<=n; i++) if(adj[i].empty()) x[i]++, y[i]++;
  sort(v.rbegin(), v.rend());
  for(auto [t, k]:v) if(t) {
    w[k]=1;
    if(w[p[k]]) Union(k, p[k], t), y[Find(k)]--;
    for(int j:adj[k]) if(w[j]) Union(k, j, t);
    for(int j:adj[k]) if(!w[j]) y[Find(k)]++;
    l[Find(k)]=t;
  }
  for(int i=1; i<=n; i++) if(w[i] && Find(i)==i) {
    tot+=x[i]*l[i], c[y[i]]+=l[i], s[y[i]]+=y[i]*l[i];
  }
  for(int i=M-2; i>=1; i--) c[i]+=c[i+1], s[i]+=s[i+1];
}

ll query(int L_, int R_) {
  ll L=L_, R=R_;
  return tot*L+s[(R+L-1)/L]*L-c[(R+L-1)/L]*R;
}

• 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