Submission #781771

#	Time	Username	Problem	Language	Result	Execution time	Memory
781771		vjudge1	Two Currencies (JOI23_currencies)	C++17	0 / 100	3 ms	4948 KiB

currencies

#include <bits/stdc++.h>

#define nl '\n'
#define V vector
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()

using namespace std;

using i64 = int64_t;

const int N = 2e5 + 5;
int a[N], n;
V<int> adj[N];
i64 ans[N];
int mxfreq[N];

struct Answer {
    map<int, int> cnt;
    i64 ans;
    int freq;
    
    Answer(int v) {
        ans = v;
        freq = 1;
        cnt[ans]++;
    }
    
    size_t size() const {
        return cnt.size();
    }
    
    void merge(const Answer& rhs) {
        for(auto& [k, v]: rhs.cnt) {
            int newVal = cnt[k] += v;
            if(newVal > freq) {
                ans = k;
                freq = newVal;
            } else if(newVal == freq) {
                ans += k;
            }
        }
    }
};

namespace std {
    void swap(Answer& lhs, Answer& rhs) {
        swap(lhs.cnt, rhs.cnt);
        swap(lhs.ans, rhs.ans);
        swap(lhs.freq, rhs.freq);
    }
}


Answer dfs(int u, int p) {
    Answer res(a[u]);
    if(adj[u].size() == 1 && adj[u][0] == p) { // leaf
        ans[u] = res.ans, mxfreq[u] = res.freq;
        return res;
    }
    for(int& v: adj[u]) {
        if(v == p) continue; 
        Answer child = dfs(v, u);
        if(child.size() > res.size()) swap(child, res);
        res.merge(child);
    }
    ans[u] = res.ans, mxfreq[u] = res.freq;
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs(0, -1);
    
    for(int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << nl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32