QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179329#6885. Simple Tree ProblemPPP#WA 7742ms359156kbC++173.8kb2023-09-14 20:37:152023-09-14 20:37:16

Judging History

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

  • [2023-09-14 20:37:16]
  • 评测
  • 测评结果:WA
  • 用时:7742ms
  • 内存:359156kb
  • [2023-09-14 20:37:15]
  • 提交

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 1000500, LOG = 20 + 2, mod = 998244353;

int n, a[N], b[N], ans[N];
vector<pair<int, pair<int, int> > > g[N];
int sz[N];

int cnt[N];

int t[N << 2][LOG], t_cnt[N][LOG];

void build(int k, int v, int tl, int tr) {
    if (tl == tr) {
        t_cnt[tl][k] = 0;
        t[v][k] = max(cnt[tl] - t_cnt[tl][k], t_cnt[tl][k]);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(k, v << 1, tl, tm);
    build(k, v << 1 | 1, tm + 1, tr);
    t[v][k] = max(t[v << 1][k], t[v << 1 | 1][k]);
}

void upd(int k, int v, int tl, int tr, int p, int x) {
    if (tl == tr) {
        t_cnt[p][k] += x;
        t[v][k] = max(cnt[p] - t_cnt[p][k], t_cnt[p][k]);
        return;
    }
    int tm = (tl + tr) >> 1;
    if (p <= tm)
        upd(k, v << 1, tl, tm, p, x);
    else
        upd(k, v << 1 | 1, tm + 1, tr, p, x);
    t[v][k] = max(t[v << 1][k], t[v << 1 | 1][k]);
}

int get(int k, int v, int tl, int tr, int x) {
    if (t[v][k] < x)
        return -1;
    if (tl == tr)
        return tl;
    int tm = (tl + tr) >> 1;
    int res = -1;
    if (res == -1)
        res = get(k, v << 1 | 1, tm + 1, tr, x);
    if (res == -1)
        res = get(k, v << 1, tl, tm, x);
    return res;
}

void dfs1(int v, int p) {
    sz[v] = 1;
    for (auto it: g[v]) {
        int to = it.first;
        if (to == p)
            continue;
        dfs1(to, v);
        sz[v] += sz[to];
    }
}

void dfs3(int v, int p, int k, int x) {
    upd(k, 1, 0, n - 1, a[v], x);
    for (auto it: g[v]) {
        int to = it.first;
        if (to == p)
            continue;
        dfs3(to, v, k, x);
    }
}

void dfs2(int v, int p, int k) {
    int u = -1;
    for (auto it: g[v]) {
        int to = it.first;
        if (to == p)
            continue;
        if (u == -1 || sz[to] > sz[u])
            u = to;
    }
    for (auto it: g[v]) {
        int to = it.first;
        if (to == p)
            continue;
        if (to == u) {
            dfs2(to, v, k);
            {
                int res = get(k, 1, 0, n - 1, it.second.first);
                if (res == -1)
                    res = 0;
                else
                    res = b[res];
                ans[it.second.second] = res;
            }
        } else {
            dfs2(to, v, k + 1);
            {
                int res = get(k + 1, 1, 0, n - 1, it.second.first);
                if (res == -1)
                    res = 0;
                else
                    res = b[res];
                ans[it.second.second] = res;
            }
            dfs3(to, v, k + 1, -1);
            dfs3(to, v, k, 1);
        }
    }
    upd(k, 1, 0, n - 1, a[v], 1);
}


void solve() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        g[i].clear();
        cnt[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(b, b + n, a[i]) - b;
        cnt[a[i]]++;
    }

    for (int i = 0; i < n - 1; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        v--, u--;
        g[v].push_back({u, {w, i}});
        g[u].push_back({v, {w, i}});
    }
    dfs1(0, 0);
    for (int i = 0; i < LOG; i++)
        build(i, 1, 0, n - 1);
    dfs2(0, 0, 0);
    for (int i = 0; i < n - 1; i++)
        cout << ans[i] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    int tst;
    cin >> tst;
    while (tst--)
        solve();

    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 7742ms
memory: 359156kb

input:

10000
96
378804736 378804736 101171470 683875564 378804736 997225055 448759149 683875564 683875564 997225055 152015654 83284224 229458933 101171470 229458933 448759149 448759149 152015654 101171470 600214219 378804736 997225055 448759149 152015654 229458933 229458933 83284224 997225055 229458933 600...

output:

997225055
997225055
0
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
997225055
99722505...

result:

wrong answer 201st lines differ - expected: '693199681', found: '680319644'