QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638667#8237. Sugar Sweet IItzwWA 52ms22072kbC++233.4kb2024-10-13 16:34:392024-10-13 16:34:40

Judging History

This is the latest submission verdict.

  • [2024-11-04 16:59:03]
  • hack成功,自动添加数据
  • (/hack/1109)
  • [2024-10-13 16:34:40]
  • Judged
  • Verdict: WA
  • Time: 52ms
  • Memory: 22072kb
  • [2024-10-13 16:34:39]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 5e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

ll qpow(ll a, ll n)
{
    ll res = 1;
    while (n)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

struct egde
{
    int to, ne;
} e[maxn];
int head[N], ecnt;

void add(int x, int y)
{
    e[++ecnt].to = y;
    e[ecnt].ne = head[x];
    head[x] = ecnt;
}

ll a[N], b[N], w[N];
int fa[N];
bool vis[N];

ll P[N];
ll ans[N], in[maxn];
bool ok = 0;

int getfa(int x)
{
    // cout << x << ' ';
    while (fa[x] != 0)
        x = fa[x];
    return x;
}

void dfs(int x, int f, int dep, bool op)
{
    vis[x] = 1;
    // cout << w[b[x] ] << ' ' << P[dep] << endl;
    if (!op)
        ans[x] = (P[dep] * w[x] % mod + a[x]) % mod;
    else
        ans[x] = a[x];
    for (int i = head[x]; i; i = e[i].ne)
    {
        int y = e[i].to;
        if (y == f)
            continue;
        dfs(y, x, dep + 1, op);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll res = 1;
    for (int i = 1; i < N; i++)
    {
        res = res * i % mod;
        P[i] = qpow(res, mod - 2) % mod;
    }
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;

        for (int i = 0; i <= n + 5; i++)
        {
            head[i] = 0;
            fa[i] = vis[i] = in[i] = 0;
        }
        ecnt = 0;

        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        for (int i = 1; i <= n; i++)
            cin >> w[i];
        for (int i = 1; i <= n; i++)
        {
            // if (i == b[i]) continue;
            if (a[i] >= a[b[i]] && a[i] < a[b[i]] + w[b[i]])
            {
                // cout << i << ' '
                if (i != b[i])
                {
                    in[i]++;
                    add(b[i], i);
                    fa[i] = b[i];
                }

                // cout << b[i] << ' ' << i << endl;
            }
        }

        // for (int i = 1; i <= n; i++)
        //     cout << fa[i] << ' ';
        // cout << endl;

        for (int i = 1; i <= n; i++)
        {
            if (!in[i])
            {
                // if (i == fa[i])
                // {
                //     ans[i] = a[i] % mod;
                //     vis[i] = 1;
                //     continue;
                // }

                // if (a[i] >= a[b[i]] + w[b[i]])
                // {
                //     // cout << i << ' ';
                //     ans[i] = a[i] % mod;
                //     vis[i] = 1;
                //     continue;
                // }

                ok = 0;
                int root = i;
                // int root = getfa(i);
                if (a[root] >= a[b[root]] + w[root])
                    ok = 1;
                if (root == b[root])
                    ok = 1;
                // cout << root << ' ';
                // if (root = 1)
                // cout << root << ' ';
                dfs(root, 0, 1, ok);
            }
        }

        for (int i = 1; i <= n; i++)
            cout << ans[i] << ' ';
        cout << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 52ms
memory: 22072kb

input:

4
4
2 5 5 2
4 2 1 3
3 2 1 4
3
5 4 3
1 1 1
6 6 6
3
5 4 3
2 3 1
1 2 3
5
2 1 3 2 1
5 1 1 3 4
1 3 4 2 4

output:

500000007 5 5 6 
5 10 9 
166666673 5 6 
500000006 4 7 4 5 

result:

wrong answer 13th numbers differ - expected: '3', found: '7'