QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#895254#8518. Roars IIIwinsunWA 2ms26468kbC++147.4kb2025-02-12 11:21:422025-02-12 11:21:44

Judging History

This is the latest submission verdict.

  • [2025-02-12 11:21:44]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 26468kb
  • [2025-02-12 11:21:42]
  • Submitted

answer

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#define fi first
#define se second
#define eb emplace_back
#define ep emplace
using namespace std;
typedef long long LL;

template <typename Tp> void read(Tp& x) {
    char ch; bool op = 0; x = 0;
    do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');
    do x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); while (ch >= '0' && ch <= '9');
    if (op) x = -x;
}
int read01() {
    char ch;
    do ch = getchar(); while (ch != '0' && ch != '1');
    return ch & 1;
}

const int mod = 998244353;
inline int fplus(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int Fplus(int& x, int y) { return x = fplus(x, y); }
inline int fminus(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
inline int Fminus(int& x, int y) { return x = fminus(x, y); }
int qpow(int x, int y = mod - 2) {
    int res = 1;
    if (x >= mod) x %= mod;
    for (; y; y >>= 1, x = 1ll * x * x % mod) if (y & 1) res = 1ll * res * x % mod;
    return res;
}
const int MAXN = 2e5+5;
int n, c[MAXN], head[MAXN], ver[MAXN<<1], nxt[MAXN<<1], tot;
void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
} 
int pa[MAXN], dep[MAXN], siz[MAXN], hvy[MAXN];
void dfs1(int x) {
    dep[x] = dep[pa[x]] + 1, siz[x] = 1, hvy[x] = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == pa[x]) continue;
        pa[y] = x;
        dfs1(y);
        siz[x] += siz[y];
        if (siz[y] > siz[hvy[x]]) hvy[x] = y;
    } 
}
int dfn[MAXN], idx[MAXN], top[MAXN], cnt;
void dfs2(int x) {
    dfn[x] = ++cnt, idx[cnt] = x;
    if (!top[x]) top[x] = x;
    if (!hvy[x]) return;
    top[hvy[x]] = top[x];
    dfs2(hvy[x]);
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == pa[x] || y == hvy[x]) continue;
        dfs2(y);
    } 
}

struct Node {
    int cnt, mx;
    LL sum;
    Node(): cnt(0), mx(-1), sum(0) {} 
    Node(int x): cnt(1), mx(x), sum(x) {}
    Node(int t, int x, LL s): cnt(t), mx(x), sum(s) {}
    friend Node operator+(const Node& x, const Node& y) {
        return Node(x.cnt+y.cnt, max(x.mx, y.mx), x.sum+y.sum);
    } 
    void app(int x) {
        if (~mx) mx += x, assert(~mx);
        sum += (LL)cnt * x;
    }
};

namespace SGT {
    Node s[MAXN<<2]; int t[MAXN<<2];
    #define mid ((l + r) >> 1)
    void build(int x, int l, int r) {
        if (l == r) {
            int u = idx[l];
            s[x] = c[u] ? Node(dep[u]) : Node(); 
            return;
        }
        build(x<<1, l, mid), build(x<<1|1, mid+1, r);
        s[x] = s[x<<1] + s[x<<1|1]; 
    }
    void addtag(int x, int l, int r, int v) {
        s[x].app(v), t[x] += v;
        if (l == r) dep[idx[l]] += v;
    }
    void spread(int x, int l, int r) {
        if (!t[x]) return;
        addtag(x<<1, l, mid, t[x]), addtag(x<<1|1, mid+1, r, t[x]);
        t[x] = 0;
    }
    void update(int x, int l, int r, int p) {
        if (l == r) {
            int u = idx[l];
            s[x] = c[u] ? Node(dep[u]) : Node(); 
            return;
        }
        spread(x, l, r);
        if (p <= mid) update(x<<1, l, mid, p);
        else update(x<<1|1, mid+1, r, p);
        s[x] = s[x<<1] + s[x<<1|1];
    }
    void add(int x, int l, int r, int L, int R, int v) {
        if (L <= l && R >= r) return addtag(x, l, r, v);
        spread(x, l, r);
        if (L <= mid) add(x<<1, l, mid, L, R, v);
        if (R > mid) add(x<<1|1, mid+1, r, L, R, v);
        s[x] = s[x<<1] + s[x<<1|1];
    } 
    int bins(int x, int l, int r) {
        if (l == r) return idx[l];
        spread(x, l, r);
        if (s[x<<1].mx >= s[x<<1|1].mx) return bins(x<<1, l, mid);
        else return bins(x<<1|1, mid+1, r);
    }
    void getseg(int x, int l, int r, int L, int R, vector<tuple<int, int, int> >& vec) {
        if (L <= l && R >= r) return vec.eb(x, l, r), void();
        spread(x, l, r);
        if (L <= mid) getseg(x<<1, l, mid, L, R, vec);
        if (R > mid) getseg(x<<1|1, mid+1, r, L, R, vec);
    }
    int vldmaxdep(int L, int R) {
        vector<tuple<int, int, int> > vec;
        getseg(1, 1, n, L, R, vec);
        int x, l, r, mxx = 0, pl = -1, pr = -1;
        for (auto tp : vec) {
            tie(x, l, r) = tp;
//            printf("x=%d, l=%d, r=%d %d\n", x, l, r, s[x].mx);
            if (!mxx || (mxx && s[x].mx > s[mxx].mx)) mxx = x, pl = l, pr = r;
        }
        assert(mxx);
        if (s[mxx].mx == -1) return -1;
        return bins(mxx, pl, pr);
    }
}

int pos[MAXN]; LL ans[MAXN];

void dfs3(int x) {
    SGT::add(1, 1, n, 1, n, 1), SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, -2);
    ans[x] = SGT::s[1].sum;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == pa[x]) continue;
        dfs3(y);
    }
    SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, 2), SGT::add(1, 1, n, 1, n, -1);
//    printf("aft%d %lld %d\n", x, SGT::s[1].sum, SGT::s[1].cnt);
}

void dfs4(int x) {
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == pa[x]) continue;
        dfs4(y);
    }
    if (c[x]) return pos[x] = x, void();
    int y = SGT::vldmaxdep(dfn[x], dfn[x] + siz[x] - 1);
//    printf("x=%d, y=%d\n", x, y);
    if (~y) {
        assert(c[y]); 
        pos[x] = y;
        c[y] = 0, c[x] = 1;
        SGT::update(1, 1, n, dfn[y]);
        SGT::update(1, 1, n, dfn[x]);
    } 
}

void dfs5(int x) {
//    printf("bef%d %lld %d\n", x, SGT::s[1].sum, SGT::s[1].cnt);
    SGT::add(1, 1, n, 1, n, 1), SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, -2);
    int p;
    if (pos[x] && pos[x] != x) {
        assert(c[x]), assert(!c[pos[x]]);
        c[pos[x]] = 1, SGT::update(1, 1, n, dfn[pos[x]]);
        p = SGT::bins(1, 1, n);
        c[p] = 0, SGT::update(1, 1, n, dfn[p]); 
//        printf("%d %d %d\n", x, pos[x], p);
    } else if (!pos[x]) {
        p = SGT::bins(1, 1, n);
        c[p] = 0, c[x] = 1; 
        SGT::update(1, 1, n, dfn[p]), SGT::update(1, 1, n, dfn[x]);
    }
    ans[x] -= SGT::s[1].sum;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == pa[x]) continue;
        dfs5(y);
    }
    if (pos[x] && pos[x] != x) {
        c[p] = 1, SGT::update(1, 1, n, dfn[p]); 
        c[pos[x]] = 0, SGT::update(1, 1, n, dfn[pos[x]]);
    } else if (!pos[x]) {
        c[p] = 1, c[x] = 0;
        SGT::update(1, 1, n, dfn[p]), SGT::update(1, 1, n, dfn[x]);
    }
    SGT::add(1, 1, n, dfn[x], dfn[x]+siz[x]-1, 2), SGT::add(1, 1, n, 1, n, -1);
//    printf("aft%d %lld %d\n", x, SGT::s[1].sum, SGT::s[1].cnt);
}

int main() {
    #ifndef ONLINE_JUDGE
    assert(freopen("qoj8518.in", "r", stdin));
    assert(freopen("qoj8518.out", "w", stdout));
    #endif
    read(n);
    for (int i = 1; i <= n; ++i) c[i] = read01();
    for (int i = 1; i < n; ++i) {
        int x, y; read(x), read(y); add(x, y), add(y, x);
    }
    dfs1(1), dfs2(1);
//    for (int i = 1; i <= n; ++i) printf("%d%c", dep[i], " \n"[i==n]); 
    SGT::build(1, 1, n);
    dfs3(1);
//    for (int i = 1; i <= n; ++i) printf("%lld%c", ans[i], " \n"[i==n]); 
    dfs4(1);
//    for (int i = 1; i <= n; ++i) printf("%d%c", c[i], " \n"[i==n]);
//    for (int i = 1; i <= n; ++i) printf("%d%c", pos[i], " \n"[i==n]);
    dfs5(1);
    for (int i = 1; i <= n; ++i) printf("%lld%c", ans[i], " \n"[i==n]); 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
10101
1 2
2 3
2 4
4 5

output:

2 2 2 3 3

result:

ok 5 number(s): "2 2 2 3 3"

Test #2:

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

input:

1
0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 24268kb

input:

1
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 26464kb

input:

2
10
1 2

output:

0 1

result:

ok 2 number(s): "0 1"

Test #5:

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

input:

3
100
2 3
2 1

output:

0 1 2

result:

ok 3 number(s): "0 1 2"

Test #6:

score: 0
Accepted
time: 2ms
memory: 26332kb

input:

4
1100
4 1
4 3
4 2

output:

1 1 3 1

result:

ok 4 number(s): "1 1 3 1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 24416kb

input:

5
10100
4 5
1 3
2 1
3 5

output:

0 2 0 4 2

result:

ok 5 number(s): "0 2 0 4 2"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 26464kb

input:

8
11001000
4 2
7 2
5 7
6 2
3 1
6 3
7 8

output:

5 1 5 4 3 3 3 6

result:

wrong answer 2nd numbers differ - expected: '3', found: '1'