QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#604434#8758. Menji 和 gcdxing4c#RE 0ms0kbC++141.1kb2024-10-02 10:53:162024-10-02 10:53:17

Judging History

This is the latest submission verdict.

  • [2024-10-02 10:53:17]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-10-02 10:53:16]
  • Submitted

answer

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int N = 2e5 + 7;
#define int long long
int n;
int w[N] = {0};
int fa[N] = {0};
vector<int> G[N];
int sum[N] = {0};
int siz[N] = {0};
int ans = 0;

bool cmp(int a, int b) {
    return 1.0 * siz[a] / sum[a] > 1.0 * siz[b] / sum[b];
}

void dfs(int u = 1) {
    for (auto to: G[u]) {
        dfs(to);
        sum[u] += sum[to];
        siz[u] += siz[to];
    }
}

int cnt = 0;

void dfs1(int u = 1) {
    cnt++;
    ans += cnt * w[u];
    sort(G[u].begin(), G[u].end(), cmp);
    for (auto to: G[u]) {
        dfs1(to);
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum[i] = w[i];
        siz[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        G[fa[i]].push_back(i);
    }
    dfs();
    dfs1();
    cout << ans;
}

signed main() {
  //  freopen("D:\\Development_Software\\CLion\\CLionProjects\\Test\\in", "r", stdin);
    ios::sync_with_stdio(false);
    int T = 1;
    while (T--)solve();
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

10
1 2
2 4
6 10
11 21
147 154
1470 1540
2890 3028
998244353 1000000007
34827364537 41029384775
147147147147 154154154154

output:


result: