QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#627702 | #5421. Factories Once More | yqr | RE | 1ms | 5900kb | C++20 | 3.8kb | 2024-10-10 16:49:15 | 2024-10-10 16:49:15 |
Judging History
answer
#include<stdio.h>
#include<ctype.h>
#include<vector>
#include<random>
#include<time.h>
// #include<assert.h>
namespace IO {
constexpr int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define gtchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<typename t> void read(t &ret)
{
int f = ret = 0;
char ch = gtchar();
while(!isdigit(ch)) f = ch == '-', ch = gtchar();
while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
if(f) ret = -ret;
}
#undef gtchar
template<typename t, typename ...T> void read(t &a, T &...b) {read(a), read(b...);}
}using IO::read;
typedef long long ll;
typedef std::pair<int, int> pii;
constexpr int maxn = 100005;
std::mt19937 rnd(std::random_device{}() ^ time(0));
int n, k, rt[maxn];
std::vector<pii> g[maxn];
struct treap {
struct node {
int l, r, size;
ll val, tag/*整体加*/, tag2/*等差数列加(+0,+d,+2d,...)*/;
unsigned int p;
}s[maxn];
int tot;
#define l(k) s[k].l
#define r(k) s[k].r
#define p(k) s[k].p
#define v(k) s[k].val
#define t(k) s[k].tag
#define t2(k) s[k].tag2
#define s(k) s[k].size
int newnode(int value)
{
int k = ++tot;
s[k] = {0, 0, 1, value, 0, 0, rnd()};
return k;
}
void add(int k, ll delta) {if(k) v(k) += delta, t(k) += delta;}
void addtag(int k, ll delta) {if(k) v(k) += delta * s(l(k)), t2(k) += delta;}
void pushdown(int k)
{
// assert(k);
if(t(k)) add(l(k), t(k)), add(r(k), t(k)), t(k) = 0;
if(t2(k)) addtag(l(k), t2(k)), add(r(k), (s(l(k)) + 1) * t2(k)), addtag(r(k), t2(k)), t2(k) = 0;
}
void pushup(int k) {s(k) = s(l(k)) + s(r(k)) + 1;}
int merge(int l, int r)
{
if(!l || !r) return l | r;
int ret;
if(p(l) < p(r)) pushdown(ret = l), r(l) = merge(r(l), r);
else pushdown(ret = r), l(r) = merge(l, l(r));
pushup(ret);
return ret;
}
void split_size(int k, int rank, int &l, int &r)
{
if(!k) return void(l = r = 0);
int tmp = s(l(k)) + 1;
pushdown(k);
if(tmp <= rank) l = k, split_size(r(k), rank - tmp, r(l), r);
else r = k, split_size(l(k), rank, l, l(r));
pushup(k);
}
void split_value(int k, ll value, int &l, int &r)
{
if(!k) return void(l = r = 0);
pushdown(k);
if(v(k) >= value) l = k, split_value(r(k), value, r(l), r);
else r = k, split_value(l(k), value, l, l(r));
pushup(k);
}
void insert(int &k, ll value)
{
int l, r;
split_value(k, value, l, r);
k = merge(merge(l, newnode(value)), r);
}
void flip(int k, std::vector<ll> &ret)
{
if(!k) return;
pushdown(k);
flip(l(k), ret);
ret.push_back(v(k));
flip(r(k), ret);
}
#undef l
#undef r
#undef p
#undef v
#undef t
#undef t2
#undef s
}tree;
void swap(int &a, int &b) {a ^= b ^= a ^= b;}
int merge(int a, int b)
{
if(tree.s[a].size > tree.s[b].size) swap(a, b);
std::vector<ll> tmp;
tree.flip(a, tmp);
for(ll v : tmp) tree.insert(b, v);
return b;
}
void dfs(int k, int pre)
{
int &now = rt[k];
now = tree.newnode(0);
for(auto i : g[k]) if(i.first != pre)
{
int to = i.first;
dfs(to, k);
int trash;
tree.add(rt[to], (ll) i.second * (::k - 1));
tree.addtag(rt[to], -2 * i.second);
now = merge(now, rt[to]);
if(tree.s[now].size > ::k) tree.split_size(now, ::k, now, trash);
}
// std::vector<ll> tmp;
// tree.flip(now, tmp);
// ll tot = 0;
// int cnt = 0;
// printf("point %d:\n", k);
// for(ll i : tmp) printf("%d:%d\n", ++cnt, tot += i);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
read(n, k);
for(int i = 1, u, v, w; i < n; i++) read(u, v, w),
g[u].push_back({v, w}), g[v].push_back({u, w});
dfs(1, -1);
std::vector<ll> tmp;
tree.flip(rt[1], tmp);
ll ans = 0;
for(ll i : tmp) ans += i;
printf("%lld\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4076kb
input:
6 3 1 2 3 2 3 2 2 4 1 1 5 2 5 6 3
output:
22
result:
ok 1 number(s): "22"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5896kb
input:
4 3 1 2 2 1 3 3 1 4 4
output:
18
result:
ok 1 number(s): "18"
Test #3:
score: 0
Accepted
time: 0ms
memory: 5900kb
input:
2 2 1 2 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Runtime Error
input:
100000 17 37253 35652 9892 56367 53643 1120 47896 49255 4547 93065 88999 1745 5251 6742 5031 49828 50972 8974 31548 46729 1032 56341 56287 4812 21896 22838 1682 82124 90557 7307 76289 76949 7028 33834 45380 6856 15499 15064 2265 10127 5251 9920 87208 93945 9487 68990 72637 6891 91640 85004 2259 4748...