提出 #52910817

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 998244353;
int n,q;
struct edge
{
    int nxt,to;
}e[maxn << 1];
int head[maxn],tot;
void add_edge(int u,int v)
{
    e[++tot].nxt = head[u];
    head[u] = tot;
    e[tot].to = v;
}
int a[maxn],b[maxn],c[maxn];

//下面是树链剖分部分
int dep[maxn],siz[maxn],dson[maxn],p[maxn];
void dfs1(int u,int fa)
{
    siz[u] = 1;
    dep[u] = dep[fa] + 1;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa)continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[dson[u]] <= siz[v])
        {
            dson[u] = v;
        }
    }
}
int rev[maxn],id[maxn],top[maxn];
int db[maxn];
int dfn;
void dfs2(int u,int topf)
{
    id[u] = ++dfn;
    top[u] = topf;
    rev[dfn] = u;
    db[topf] = u;
    if(!dson[u])return ;
    dfs2(dson[u],topf);
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v != p[u] && v != dson[u])dfs2(v,v);
    }
}
//上面是树链剖分部分

//下面是线段树

struct Segment1
{
    #define ls p << 1
    #define rs p << 1 | 1
    int tr[maxn << 2];
    void push_up(int p)
    {
        tr[p] = tr[ls] * tr[rs] % mod;
    }
    void build(int p,int l,int r)
    {
        if(l == r)return tr[p] = a[p],void();
        int mid = l + r >> 1;
        build(ls,l,mid);
        build(rs,mid + 1,r);
        push_up(p);
    }
    int query(int p,int l,int r,int L,int R)
    {
        if(L <= l && r <= R)return tr[p];
        int mid = l + r >> 1;
        int ans = 1;
        if(L <= mid)ans = ans * query(ls,l,mid,L,R) % mod;
        if(R > mid)ans = ans * query(rs,mid + 1,r,L,R) % mod;
        return ans;
    }
    void update(int p,int l,int r,int pos,int x)
    {
        if(l == r)return tr[p] = x,void();
        int mid = l + r >> 1;
        if(pos <= mid)update(ls,l,mid,pos,x);
        if(pos > mid)update(rs,mid + 1,r,pos,x);
        push_up(p);
    }
    #undef ls
    #undef rs
}A;//这是第一棵，用来维护乘积

struct Segment2
{
    #define ls p << 1
    #define rs p << 1 | 1
    struct node
    {
        int sum,mul;
    }tr[maxn << 2];
    void push_up(int p)
    {
        tr[p].sum = (tr[ls].sum + tr[ls].mul * tr[rs].sum % mod) % mod;
        tr[p].mul = tr[ls].mul * tr[rs].mul % mod;
    }
    void build(int p,int l,int r)
    {
        if(l == r)
        {
            tr[p].sum = a[rev[l]];
            tr[p].mul = b[rev[l]];
            return ;
        }
        int mid = l + r >> 1;
        build(ls,l,mid);
        build(rs,mid + 1,r);
        push_up(p);
    }
    void update(int p,int l,int r,int pos)
    {
        if(l == r)
        {
            tr[p].sum = a[rev[l]];
            tr[p].mul = b[rev[l]];
            return ;
        }
        int mid = l + r >> 1;
        if(pos <= mid)update(ls,l,mid,pos);
        else update(rs,mid + 1,r,pos);
        push_up(p);
    }
    node query(int p,int l,int r,int L,int R)
    {
        if(L <= l && r <= R)
        {
            return tr[p];
        }
        int mid = l + r >> 1;
        if(L <= mid && mid < R)
        {
            node u = query(ls,l,mid,L,R),v = query(rs,mid + 1,r,L,R);
            return {(u.sum + u.mul * v.sum % mod) % mod,u.mul * v.mul % mod};
        }
        else if(L <= mid)return query(ls,l,mid,L,R);
        else return query(rs,mid + 1,r,L,R);
    }
}B;

//上面是线段树

int L[maxn],R[maxn];
int tot2;
int dfn2[maxn];

void dfs3(int u)
{
    L[u] = tot2 + 1;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v != p[u] && v != dson[u])dfn2[v] = ++tot2;
    }
    R[u] = tot2;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == p[u])continue;
        dfs3(v);
    }
}

int ask(int x)
{
    return A.query(1,1,tot2,L[x],R[x]);
}

void dfs4(int u)
{
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == p[u])continue;
        dfs4(v);
    }
    b[u] = ask(u);
    if(dson[u])c[u] = (a[u] + b[u] * c[dson[u]] % mod) % mod;
    else c[u] = a[u];
    if(dfn2[u])A.update(1,1,tot2,dfn2[u],c[u]);
}

signed main()
{
    cin >> n >> q;
    for(int i = 2;i <= n;i++)
    {
        cin >> p[i];
        add_edge(i,p[i]);
        add_edge(p[i],i);
    }
    for(int i = 1;i <= n;i++)cin >> a[i];
    dfs1(1,0);
    dfs2(1,1);
    dfn2[1] = 1;
    tot2 = 1;
    dfs3(1);
    A.build(1,1,tot2);
    dfs4(1);
    B.build(1,1,n);
    while(q--)
    {
        int u,v;
        cin >> u >> v;
        a[u] = v;
        while(u)
        {
            B.update(1,1,n,id[u]);
            if(p[top[u]])
            {
                A.update(1,1,tot2,dfn2[top[u]],B.query(1,1,n,id[top[u]],id[db[top[u]]]).sum);
                b[p[top[u]]] = ask(p[top[u]]);
            }
            u = p[top[u]];
        }
        cout << B.query(1,1,n,id[1],id[db[1]]).sum << '\n';
    }
    return 0;
}

提出情報

提出日時
問題 G - Hash on Tree
ユーザ feather_life
言語 C++ 20 (gcc 12.2)
得点 650
コード長 5160 Byte
結果 AC
実行時間 1541 ms
メモリ 51024 KiB

コンパイルエラー

Main.cpp: In member function ‘void Segment1::build(long long int, long long int, long long int)’:
Main.cpp:71:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function ‘long long int Segment1::query(long long int, long long int, long long int, long long int, long long int)’:
Main.cpp:79:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   79 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function ‘void Segment1::update(long long int, long long int, long long int, long long int, long long int)’:
Main.cpp:88:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   88 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function ‘void Segment2::build(long long int, long long int, long long int)’:
Main.cpp:118:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  118 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function ‘void Segment2::update(long long int, long long int, long long int, long long int)’:
Main.cpp:131:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  131 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function ‘Segment2::node Segment2::query(long long int, long long int, long long int, long long int, long long int)’:
Main.cpp:142:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
  142 |         int mid = l + r >> 1;
      |                   ~~^~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 650 / 650
結果
AC × 3
AC × 46
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 02_random_max_00.txt, 02_random_max_01.txt, 02_random_max_02.txt, 02_random_max_03.txt, 03_path_00.txt, 04_star_00.txt, 04_star_01.txt, 04_star_02.txt, 04_star_03.txt, 05_centipede_00.txt, 05_centipede_01.txt, 05_centipede_02.txt, 05_centipede_03.txt, 05_centipede_04.txt, 05_centipede_05.txt, 05_centipede_06.txt, 05_centipede_07.txt, 05_centipede_08.txt, 05_centipede_09.txt, 05_centipede_10.txt, 05_centipede_11.txt, 06_n-ary_00.txt, 06_n-ary_01.txt, 06_n-ary_02.txt, 06_n-ary_03.txt, 06_n-ary_04.txt, 06_n-ary_05.txt, 06_n-ary_06.txt, 06_n-ary_07.txt, 06_n-ary_08.txt, 06_n-ary_09.txt, 07_corner_00.txt, 08_hld_worst_complexity_00.txt, 08_hld_worst_complexity_01.txt, 08_hld_worst_complexity_02.txt, 08_hld_worst_complexity_03.txt, 08_hld_worst_complexity_04.txt, 09_corner_2_00.txt, 09_corner_2_01.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 1 ms 3672 KiB
00_sample_01.txt AC 1 ms 3656 KiB
00_sample_02.txt AC 1 ms 3716 KiB
01_random_00.txt AC 1182 ms 40176 KiB
01_random_01.txt AC 1159 ms 39080 KiB
01_random_02.txt AC 1117 ms 36992 KiB
01_random_03.txt AC 794 ms 14380 KiB
02_random_max_00.txt AC 1222 ms 43684 KiB
02_random_max_01.txt AC 1219 ms 43676 KiB
02_random_max_02.txt AC 1214 ms 43588 KiB
02_random_max_03.txt AC 1225 ms 43492 KiB
03_path_00.txt AC 519 ms 51024 KiB
04_star_00.txt AC 681 ms 40836 KiB
04_star_01.txt AC 688 ms 44008 KiB
04_star_02.txt AC 709 ms 44616 KiB
04_star_03.txt AC 689 ms 43924 KiB
05_centipede_00.txt AC 620 ms 49268 KiB
05_centipede_01.txt AC 653 ms 49376 KiB
05_centipede_02.txt AC 663 ms 47440 KiB
05_centipede_03.txt AC 709 ms 47400 KiB
05_centipede_04.txt AC 740 ms 45700 KiB
05_centipede_05.txt AC 850 ms 44944 KiB
05_centipede_06.txt AC 744 ms 45352 KiB
05_centipede_07.txt AC 846 ms 45544 KiB
05_centipede_08.txt AC 695 ms 47744 KiB
05_centipede_09.txt AC 691 ms 47676 KiB
05_centipede_10.txt AC 748 ms 46700 KiB
05_centipede_11.txt AC 742 ms 46644 KiB
06_n-ary_00.txt AC 1488 ms 42736 KiB
06_n-ary_01.txt AC 1398 ms 44588 KiB
06_n-ary_02.txt AC 1248 ms 44292 KiB
06_n-ary_03.txt AC 1123 ms 44104 KiB
06_n-ary_04.txt AC 891 ms 44084 KiB
06_n-ary_05.txt AC 790 ms 43980 KiB
06_n-ary_06.txt AC 767 ms 44084 KiB
06_n-ary_07.txt AC 698 ms 44016 KiB
06_n-ary_08.txt AC 1515 ms 43984 KiB
06_n-ary_09.txt AC 1541 ms 44552 KiB
07_corner_00.txt AC 654 ms 49760 KiB
08_hld_worst_complexity_00.txt AC 1466 ms 45596 KiB
08_hld_worst_complexity_01.txt AC 1428 ms 45652 KiB
08_hld_worst_complexity_02.txt AC 1276 ms 43648 KiB
08_hld_worst_complexity_03.txt AC 1114 ms 43752 KiB
08_hld_worst_complexity_04.txt AC 936 ms 44300 KiB
09_corner_2_00.txt AC 394 ms 6084 KiB
09_corner_2_01.txt AC 595 ms 44204 KiB