QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628419#8237. Sugar Sweet IIzzfsTL 1395ms15244kbC++149.6kb2024-10-10 20:07:002024-10-10 20:07:05

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 16:59:03]
  • hack成功，自动添加数据
  • (/hack/1109)
  • [2024-10-10 20:07:05]
  • 评测
  • 测评结果：TL
  • 用时：1395ms
  • 内存：15244kb
查看
  • [2024-10-10 20:07:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define mod_n 1000000007
#define mod(x) ((x) % mod_n)
#define int int64_t
#define max_len 500010

int qpow(int x, int n)
{
    if (n == 0)
        return 1;
    else if (n == 1)
        return mod(x);
    else if (n % 2 == 0)
        return qpow(mod(x * x), n / 2);
    else
        return mod(qpow(mod(x * x), n / 2) * x);
}

int inv_save[max_len];
bool is_invinit = false;

int inv1(int x)
{
    return qpow(x, mod_n - 2);
}

void inv_init()
{
    for (int i = 1; i < max_len; i++)
    {
        inv_save[i] = inv1(i);
    }
}

int inv(int x)
{
    if (x < max_len)
        return inv_save[x];
    else
        return inv1(x);
}

int inv_jc_arr[max_len];
void init_inv_jc()
{
    inv_jc_arr[0] = inv_jc_arr[1] = 1;
    for (int i = 2; i < max_len; i++)
    {
        inv_jc_arr[i] = mod(inv_jc_arr[i - 1] * inv(i));
    }
}

struct node
{
    int p_next;
    int have_sugar;
    int will_add;

    int E_val;
    int len;

    bool dfs1_vis;
    bool dfs2_vis;
    bool duan;
    int change_E;
} node_arr[max_len];

int in_stack[max_len];
vector<int> stk_vec;

/*void dfs1(int now_i)
{
    if (node_arr[now_i].dfs1_vis == true)
    {
        return;
    }
    if (in_stack[now_i] == 0)
    {
        in_stack[now_i] = stk_vec.size();
        stk_vec.push_back(now_i);
        dfs1(node_arr[now_i].p_next);

        node_arr[now_i].dfs1_vis = true;
        stk_vec.pop_back();
        in_stack[now_i] = 0;
    }
    else // huan
    {
        int huan_len = stk_vec.size() - in_stack[now_i];
        int base_len = in_stack[now_i];
        for (int i = 0; i < huan_len; i++)
        {
            int ni = stk_vec[base_len + (huan_len + i) % huan_len];
            int ni_nx = node_arr[ni].p_next;

            if (node_arr[ni].have_sugar < node_arr[ni_nx].have_sugar)
            {
                node_arr[ni].change_E = 1;
                node_arr[ni].duan = true;
                node_arr[ni].p_next = ni;
                // break;
            }
            else if (node_arr[ni].have_sugar >= node_arr[ni_nx].have_sugar +
                                                    node_arr[ni_nx].will_add)
            {

                node_arr[ni].change_E = 0;
                node_arr[ni].p_next = ni;
                // break;
            }
        }
    }
}*/

struct dfs_info
{
    int now_i;
    int lev;
};

void dfs1(int now_i_beg)
{
    stack<dfs_info> dfs_stk;
    dfs_stk.push({now_i_beg, 0});
    while (dfs_stk.size() != 0)
    {
        auto [now_i, lev] = dfs_stk.top();
        dfs_stk.pop();
        if (node_arr[now_i].dfs1_vis == true)
        {
            continue;
        }
        if (in_stack[now_i] == 0)
        {
            if (lev == 0)
            {
                in_stack[now_i] = stk_vec.size();
                stk_vec.push_back(now_i);
                // dfs1(node_arr[now_i].p_next);
                dfs_stk.push({now_i, 1});
                dfs_stk.push({node_arr[now_i].p_next, 0});
            }
            else
            {
                node_arr[now_i].dfs1_vis = true;
                stk_vec.pop_back();
                in_stack[now_i] = 0;
            }
        }
        else // huan
        {
            int huan_len = stk_vec.size() - in_stack[now_i];
            int base_len = in_stack[now_i];
            for (int i = 0; i < huan_len; i++)
            {
                int ni = stk_vec[base_len + (huan_len + i) % huan_len];
                int ni_nx = node_arr[ni].p_next;

                if (node_arr[ni].have_sugar < node_arr[ni_nx].have_sugar)
                {
                    node_arr[ni].change_E = 1;
                    node_arr[ni].duan = true;
                    node_arr[ni].p_next = ni;
                    // break;
                }
                else if (node_arr[ni].have_sugar >= node_arr[ni_nx].have_sugar +
                                                        node_arr[ni_nx].will_add)
                {

                    node_arr[ni].change_E = 0;
                    node_arr[ni].p_next = ni;
                    // break;
                }
            }
        }
    }
}

/*int dfs2(int now_i)
{
    node_arr[now_i].dfs2_vis = true;
    if (node_arr[now_i].len != -1)
    {
        return node_arr[now_i].len;
    }
    if (node_arr[now_i].p_next == now_i)
    {
        node_arr[now_i].E_val = node_arr[now_i].have_sugar;
        if (node_arr[now_i].duan == true)
        {
            node_arr[now_i].change_E = 1;
            node_arr[now_i].E_val += node_arr[now_i].will_add;
        }
        node_arr[now_i].E_val = mod(node_arr[now_i].E_val);
        node_arr[now_i].len = 0;
        return 0;
    }
    else
    {
        int len = dfs2(node_arr[now_i].p_next);
        int pnx = node_arr[now_i].p_next;
        node_arr[now_i].E_val = node_arr[now_i].have_sugar;
        if (node_arr[now_i].have_sugar >= node_arr[pnx].have_sugar)
        {
            if (node_arr[now_i].have_sugar < node_arr[pnx].have_sugar +
                                                 node_arr[pnx].will_add)
            {
                node_arr[now_i].change_E = mod(inv(len + 2) * node_arr[pnx].change_E);
                node_arr[now_i].E_val +=
                    mod(node_arr[now_i].will_add * node_arr[now_i].change_E);

                node_arr[now_i].E_val = mod(node_arr[now_i].E_val);

                len = len + 1;
            }
            else
            {
                node_arr[now_i].change_E = 0;
                len = 0;
            }
        }
        else
        {
            node_arr[now_i].change_E = 1;
            node_arr[now_i].E_val += node_arr[now_i].will_add;
            node_arr[now_i].E_val = mod(node_arr[now_i].E_val);
            len = 0;
        }
        node_arr[now_i].len = len;
        return len;
    }
}*/

void dfs2(int now_i_beg)
{
    stack<dfs_info> dfs_stk;
    dfs_stk.push({now_i_beg, 0});
    while (dfs_stk.size() != 0)
    {
        auto [now_i, lev] = dfs_stk.top();
        dfs_stk.pop();

        node_arr[now_i].dfs2_vis = true;
        if (node_arr[now_i].len != -1)
        {
            continue;
            // return node_arr[now_i].len;
        }
        if (node_arr[now_i].p_next == now_i)
        {
            node_arr[now_i].E_val = node_arr[now_i].have_sugar;
            if (node_arr[now_i].duan == true)
            {
                node_arr[now_i].change_E = 1;
                node_arr[now_i].E_val += node_arr[now_i].will_add;
            }
            node_arr[now_i].E_val = mod(node_arr[now_i].E_val);
            node_arr[now_i].len = 0;
            // return 0;
            continue;
        }
        else
        {
            if (lev == 0)
            {
                dfs_stk.push({now_i, 1});
                dfs_stk.push({node_arr[now_i].p_next, 0});
                // int len = dfs2(node_arr[now_i].p_next);
            }
            else
            {
                int len = node_arr[node_arr[now_i].p_next].len;
                int pnx = node_arr[now_i].p_next;
                node_arr[now_i].E_val = node_arr[now_i].have_sugar;
                if (node_arr[now_i].have_sugar >= node_arr[pnx].have_sugar)
                {
                    if (node_arr[now_i].have_sugar < node_arr[pnx].have_sugar +
                                                         node_arr[pnx].will_add)
                    {
                        node_arr[now_i].change_E = mod(inv(len + 2) * node_arr[pnx].change_E);
                        node_arr[now_i].E_val +=
                            mod(node_arr[now_i].will_add * node_arr[now_i].change_E);

                        node_arr[now_i].E_val = mod(node_arr[now_i].E_val);

                        len = len + 1;
                    }
                    else
                    {
                        node_arr[now_i].change_E = 0;
                        len = 0;
                    }
                }
                else
                {
                    node_arr[now_i].change_E = 1;
                    node_arr[now_i].E_val += node_arr[now_i].will_add;
                    node_arr[now_i].E_val = mod(node_arr[now_i].E_val);
                    len = 0;
                }
                node_arr[now_i].len = len;
                // return len;
            }
        }
    }
}

void init_arr(int N)
{
    stk_vec.clear();
    for (int i = 0; i < N + 10; i++)
    {
        in_stack[i] = 0;
        node_arr[i].len = -1;
        node_arr[i].E_val = 0;
        node_arr[i].change_E = 0;

        node_arr[i].dfs1_vis = false;
        node_arr[i].dfs2_vis = false;
        node_arr[i].duan = false;
    }
}

void sol()
{
    int N;
    cin >> N;
    init_arr(N);

    for (int i = 1; i <= N; i++)
    {
        cin >> node_arr[i].have_sugar;
    }
    for (int i = 1; i <= N; i++)
    {
        cin >> node_arr[i].p_next;
    }
    for (int i = 1; i <= N; i++)
    {
        cin >> node_arr[i].will_add;
    }
    for (int i = 1; i <= N; i++)
    {
        if (node_arr[i].dfs1_vis == false)
        {
            dfs1(i);
        }
    }
    for (int i = 1; i <= N; i++)
    {
        if (node_arr[i].dfs2_vis == false)
        {
            dfs2(i);
        }
    }
    for (int i = 1; i <= N; i++)
    {
        cout << node_arr[i].E_val << (i == N ? '\n' : ' ');
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    inv_init();
    init_inv_jc();
    int T;
    cin >> T;
    while (T--)
    {
        sol();
    }
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 70ms
memory: 15176kb

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 3 4 5

result:

ok 15 numbers

Test #2:

score: 0
Accepted
time: 257ms
memory: 14048kb

input:

50000
5
508432375 168140163 892620793 578579275 251380640
3 4 4 1 3
346232959 736203130 186940774 655629320 607743104
1
863886789
1
364158084
18
864679185 463975750 558804051 604216585 694033700 499417132 375390750 337590759 467353355 111206671 983760005 984444619 322277587 138763925 205122047 97736...

output:

854665334 904343293 590444253 906393935 859123744
863886789
871186919 814243920 968784984 206455474 17527050 449261413 196759729 901433117 519383814 907574792 983760005 984444619 489899014 435736558 113628626 977360756 482247153 963066959
665922935 577926775 132646723 421298438 601054667 99438820 94...

result:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 347ms
memory: 15244kb

input:

5000
32
770948244 768935990 679008477 140059459 126718762 172369567 60723299 139563987 671220914 149354390 157693423 281776861 412464718 869245476 446234952 827569915 294423239 672541652 309942421 252597259 603376135 207343159 409718246 366254256 59153054 589167713 171168426 802508752 545258815 7373...

output:

351791786 607445427 53351025 96277100 671164280 94237502 491532542 689573864 38427324 382704130 816373728 309284273 690430261 869245476 291526004 827569915 99656414 748890295 609504084 467918578 603376135 501064338 501009010 85120176 17055939 969361082 892391697 802508752 545258815 333168524 1165920...

result:

ok 500000 numbers

Test #4:

score: 0
Accepted
time: 1395ms
memory: 14804kb

input:

500
831
941014154 653817226 737317394 548891909 650240324 784152288 337897920 919008275 807254058 243382923 935726688 583553418 88833789 750399807 577623567 595406246 982133524 532836513 286249019 780939608 102125785 501372622 567570217 761966021 24185161 261377492 548514161 60622277 424507766 53868...

output:

230438528 510098604 738011151 548891909 580268181 784152288 162823835 919008275 807254058 787780699 169718491 688535564 555077367 834193932 577623567 199204617 982133524 727940533 893934195 780939608 85179822 570950549 313144085 761966021 26675845 421401245 433344217 526647729 682184775 211847212 73...

result:

ok 500000 numbers

Test #5:

score: -100
Time Limit Exceeded

input:

50
15547
79925051 123631785 451773599 290189979 8044136 985464173 25844832 289071231 239507420 289791589 915514277 479789432 442504231 802244771 740816861 403881580 976651260 224945729 212313439 170590725 774102963 484364764 878553828 980521523 949147335 322115091 853616905 280879526 946658136 41530...

output:

284534137 370503506 451773599 700040615 326578027 985464173 354118840 239415089 726041909 289791589 556747412 978820837 939334538 802244771 214118527 173005433 375935904 451502781 253004725 744007077 774102963 484364764 542287768 980521523 949147335 322115091 853616905 154636248 189607066 65863811 8...

result:
English 繁體中文 简体中文

服务器时间: 2025-01-21 06:26:06 | 开源项目