QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523615#5041. FireAndyqian7WA 1ms5932kbC++203.4kb2024-08-18 14:57:042024-08-18 14:57:05

Judging History

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

  • [2024-08-18 14:57:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5932kb
  • [2024-08-18 14:57:04]
  • 提交

answer

#include <bits/stdc++.h>
#define lowbit(x) x & -x
#define rep(i, s, e) for (int i = s; i <= e; i++)
using namespace std;
const int MAX = 1e5 + 10;
int n, m, k, a[MAX], f[MAX], g[MAX], sz[MAX];
vector<int> nei[MAX], sons[MAX];
void build(int s)
{
    sz[s] = 1;
    for (int n : nei[s])
    {
        if (sz[n])
            continue;
        build(n);
        sz[s] += sz[n];
        sons[s].push_back(n);
    }
}
struct node
{
    int dp, sz;
    friend bool operator<(const node &x, const node &y)
    {
        return x.sz > y.sz;
    }
};
void dfs(int s)
{
    for (int son : sons[s])
    {
        dfs(son);
    }
    int l = -1, r = a[s] + k - 2 * (sz[s] - 1) - 2;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        vector<node> v;
        m = sons[s].size();
        for (int son : sons[s])
        {
            v.push_back({f[son], sz[son]});
        }
        sort(v.begin(), v.end(), [](const node &x, const node &y)
             { return x.dp + 2 * x.sz > y.dp + 2 * y.sz; });
        priority_queue<node> Q;
        int tmp = mid + 2 * (sz[s] - 1) + 1, pos = 0, sum = 0; // sum of 2*sz not inclusive
        bool sign = 1;
        rep(i, 1, m)
        {
            for (; pos < m && sum + v[pos].dp + 2 * v[pos].sz >= tmp; pos++)
            {
                Q.push(v[pos]);
            }
            if (Q.empty())
            {
                sign = 0;
                break;
            }
            auto [dp, sz] = Q.top();
            Q.pop();
            sum += 2 * sz;
        }
        if (sign)
            l = mid;
        else
            r = mid - 1;
    }
    f[s] = l;
    if (sons[s].empty())
    {
        g[s] = max(-1, a[s] - 1);
        return;
    }
    l = -1, r = a[s] + k;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        int ma = -1e9, mapo = -1;
        for (int son : sons[s])
        {
            if (g[son] + 2 * sz[son] >= mid + 2 * sz[s] - 1 && sz[son] > ma)
            {
                mapo = son;
                ma = sz[son];
            }
        }
        bool sign = 1;
        if (mapo == -1)
            sign = 0;
        if (a[s] + k - mid - 2 * (sz[s] - ma) < 0)
            sign = 0;
        vector<node> v;
        for (int son : sons[s])
        {
            if (son != mapo)
            {
                v.push_back({f[son], sz[son]});
            }
        }
        sort(v.begin(), v.end(), [](const node &x, const node &y)
             { return x.dp + 2 * x.sz > y.dp + 2 * y.sz; });
        priority_queue<node> Q;
        m = v.size();
        int tmp = mid + 2 * (sz[s] - 1 - sz[mapo]) + 1, pos = 0, sum = 0; // sum of 2*sz not inclusive
        rep(i, 1, m)
        {
            for (; pos < m && sum + v[pos].dp + 2 * v[pos].sz >= tmp; pos++)
            {
                Q.push(v[pos]);
            }
            if (Q.empty())
            {
                sign = 0;
                break;
            }
            auto [dp, sz] = Q.top();
            Q.pop();
            sum += 2 * sz;
        }
        if (sign)
            l = mid;
        else
            r = mid - 1;
    }
    g[s] = l;
}
int main()
{
    cin >> n >> k;
    rep(i, 1, n - 1)
    {
        int x, y;
        cin >> x >> y;
        nei[x].push_back(y), nei[y].push_back(x);
    }
    build(1);
    rep(i, 1, n) cin >> a[i];
    dfs(1);
    cout << g[1];
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5688kb

input:

3 1
1 2
1 3
4 3 5

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5932kb

input:

3 1
1 2
1 3
2 10 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

2 0
1 2
10 10

output:

8

result:

ok 1 number(s): "8"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5928kb

input:

3 0
1 2
3 1
10 8 10

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3592kb

input:

10 0
9 7
2 7
2 1
4 7
9 6
7 3
8 10
9 10
8 5
29 24 27 22 20 25 23 29 20 20

output:

7

result:

wrong answer 1st numbers differ - expected: '8', found: '7'