QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#536684#5102. Dungeon CrawlerRngBased#WA 0ms3596kbC++202.4kb2024-08-29 15:44:092024-08-29 15:44:09

Judging History

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

  • [2024-08-29 15:44:09]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3596kb
  • [2024-08-29 15:44:09]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pi3 tuple<int, int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;

struct sparse
{
    static const int P = 12;
    ll n, table[2005][P];
    void init(int _n)
    {
        n = _n;
        for (int i = 1; i <= n; i++)
            table[i][0] = 0;
    }
    void set(int p, ll v)
    {
        table[p][0] = v;
    }
    void build()
    {
        for (int p = 0; p + 1 < P; p++)
            for (int i = 1; (i + (1 << p)) <= n; i++)
                table[i][p + 1] = max(table[i][p], table[i + (1 << p)][p + 1]);
    }
    ll query(int l, int r)
    {
        if (r < l) return 0;
        int lg = __lg(r - l + 1);
        return max(table[l][lg], table[r - (1 << lg) + 1][lg]);
    }
} st;

int n, q, vis[2005], t;
ll ans[200005], d[2005], sum;
pii io[2005];
vector<pi3> qs[2005];
vector<pll> E[2005];

void dfs(int u)
{
    io[u].F = ++t;
    vis[u] = 1;
    for (auto [v, w] : E[u])
        if (!vis[v])
        {
            d[v] = d[u] + w;
            dfs(v);
        }
    io[u].S = t;
}

bool is_child(int r, int c)
{
    return io[r].F <= io[c].F && io[c].S <= io[r].S;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        E[u].emplace_back(v, w);
        E[v].emplace_back(u, w);
        sum += 2 * w;
    }
    for (int i = 1; i <= q; i++)
    {
        int s, k, t;
        cin >> s >> k >> t;
        qs[s].emplace_back(k, t, i);
    }
    for (int r = 1; r <= n; r++)
    {
        t = 0, d[r] = 0;
        fill(vis + 1, vis + 1 + n, 0);
        dfs(r);
        st.init(n);
        for (int i = 1; i <= n; i++)
            st.set(io[i].F, d[i]);
        st.build();
        for (auto [key, trap, i] : qs[r])
        {
            if (is_child(key, trap))
                ans[i] = -st.query(1, n);
            else if (is_child(trap, key))
                ans[i] = 1;
            else 
                ans[i] = -max(st.query(1, io[key].F - 1), st.query(io[key].S + 1, n));
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (ans[i] > 0)
            cout << "impossible\n";
        else 
            cout << sum + ans[i] << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3596kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

301
313
329
impossible
307

result:

wrong answer 1st lines differ - expected: '316', found: '301'