/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 1ms 532.0 KiB
#2 Wrong Answer 131ms 2.668 MiB

Code

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define int ll
# define double long double
const int N = 2e5 + 2, MOD = 1e9 + 7;
#define deb(x) cout<<#x<<"="<<x<<endl;
#define F first
#define S second
int n;
vector<vector<int>> adj;
vector<char> vals;
vector<int> in;
vector<int> out;
int timer{};

struct node {
    char c;
    int a[27];

    node() {
        memset(a, 0, sizeof a);
//        c = 'z';
    }
};

struct SEGT {
    int sz = 1;
    vector<node> seg;

    node op(node a, node b) {
        int mx{};
        char tmp = 'a';
        for (int i = 0; i < 26; ++i) {
            a.a[i] += b.a[i];
            if (a.a[i] > mx) {
                mx = a.a[i];
                tmp = char(i + 'a');
            }
        }
        a.c = tmp;
        return a;
    }

    void update(int i, char v, int x, int lx, int rx) {
        if (lx == rx) {
            for (int j = 0; j < 26; ++j) {
                seg[x].a[j] = 0;
            }
            seg[x].c = v;
            seg[x].a[v - 'a']++;
            return;
        }
        int md = (lx + rx) >> 1;
        if (i <= md) {
            update(i, v, 2 * x + 1, lx, md);
        } else {
            update(i, v, 2 * x + 2, md + 1, rx);
        }
        seg[x] = op(seg[2 * x + 1], seg[2 * x + 2]);

    }

    node query(int l, int r, int x, int lx, int rx) {
        if (r < lx or rx < l) {
            return {};
        }
        if (l <= lx and rx <= r) {
            return seg[x];
        }
        ll mid = (lx + rx) >> 1;
        return op(query(l, r, 2 * x + 1, lx, mid), query(l, r, 2 * x + 2, mid + 1, rx));
    }

public:
    SEGT(int n) {
        sz = 1;
        while (sz < n) { sz <<= 1; }
        seg = vector<node>(sz << 1);
    }

    void update(int i, char v) {
        update(i, v, 0, 0, sz - 1);
    }

    char query(int l, int r) {
        return query(l, r, 0, 0, sz - 1).c;
    }
};


void dfs(int u, int par) {
    in[u] = timer++;
    for (auto it: adj[u]) {
        if (it == par)continue;
        dfs(it, u);
    }
    out[u] = timer - 1;
}


void solve() {
    cin >> n;
    adj = vector<vector<int>>(n + 1);
    vals = vector<char>(n + 1);
    in = vector<int>(n + 1);
    out = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> vals[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    SEGT seg(n + 1);
    for (int i = 1; i <= n; ++i) {
        seg.update(in[i], vals[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        int ty, u;
        cin >> ty >> u;
        if (ty == 1) {
            char c;
            cin >> c;
            seg.update(in[u], c);
        } else {
            cout << seg.query(in[u], out[u]) << "\n";
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
//#ifndef ONLINE_JUDGE
//    freopen("output.txt", "w", stdout);
//    freopen("input.txt", "r", stdin);
//#endif
    int tt = 1;
//    cin >> tt;
    for (int i = 0; i < tt; i++) {
//        cout << "Case " << i + 1 << ": ";
        solve();
        cout << "\n";
    }
}

Information

Submit By
Type
Submission
Problem
P1091 Alphabetical Kingdom
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 16:33:08
Judged At
2024-11-11 03:00:19
Judged By
Score
0
Total Time
131ms
Peak Memory
2.668 MiB