Submission #1237345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237345		rewrejfsfo	Magic Tree (CEOI19_magictree)	C++20	3 / 100	104 ms	45396 KiB

magictree

//(^._.^)ﾉ Meow
//From Truong with love
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long
#define lb long double
#define forr(i,x,y) for(int i=x;i>=y;--i)
#define ford(i,x,y) for(int i=x;i<=y;++i)
#define pb push_back
#define pf push_front
#define vll vector<ll>
#define pll pair<ll,ll>
#define ii pair<int,int>
#define mmb(v,c) memset(v,c,sizeof(v))
#define fi first
#define se second
#define isz(x) x.size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define __ <<" "<<
#define fiset(x) fixed<<setprecision(x)
#define cach(i,n,c1,c2) (i==n?c1:c2)
#define file(name) freopen(name".inp","r",stdin);freopen(name".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const ll inf=1e18;
const lb EPS=1e-15;
const int N=1e5+6;
int minmize(int a,int b){return (a<b?a:b);}
int maxmize(int a,int b){return (a>b?a:b);}
ll Minmize(ll a,ll b){return (a<b?a:b);}
ll Maxmize(ll a,ll b){return (a>b?a:b);}
int n,m,k,p[N],t[N],d[N],w[N],tin[N],tout[N],timer;
ll BIT[N],dp[N],c[N];
vector<int>adj[N],day[N],stt;
vector<ii>f[N];
unordered_map<int,ll>ump[N];
void update(int id,ll val)
{
    while(id<=n)
    {
        BIT[id]+=val;
        id+=id&-id;
    }
}
ll query(int id)
{
    ll s=0;
    while(id>0)
    {
        s+=BIT[id];
        id-=id&-id;
    }
    return s;
}
ll range(int l,int r)
{
    if(l>r)
        return 0;
    return query(r)-query(l-1);
}
void DFS(int u)
{
    tin[u]=++timer;
    for(auto&v:adj[u])
        DFS(v);
    tout[u]=timer;
    stt.pb(u);
}
void kosetsu()
{
    /*
    - Coi ngày là 1 đoạn thẳng quản lí bằng BIT
    - Gọi dp[u] là tổng max ở đỉnh là u, c[u] là tổng trong 1 vài ngày liên tiếp
    - Xét lần lượt [1, k] ngày rồi cập nhật lại mảng c
    * Nhận xet, thời gian cập nhật = tin[u], tout[u]
    - Cuối dùng quy hoạch động từ con lên gốc 1
    */
}
void nguu()
{
    cin>>n>>m>>k;
    ford(i,2,n)
    {
        cin>>p[i];
        adj[p[i]].pb(i);
        //adj[i].pb(p[i]);
    }
    ford(i,1,m)
    {
        cin>>t[i]>>d[i]>>w[i];
        day[d[i]].pb(i);
    }
    DFS(1);
    //mmb(c,-1);
    ford(u,1,n)
        c[u]=-inf;
    ford(i,1,k)
    {
        for(auto&j:day[i])
        {
            int u=t[j];
            update(tin[u],w[j]);
        }
        for(auto&j:day[i])
        {
            int u=t[j];
            c[u]=Maxmize(c[u],range(tin[u],tout[u]));
        }
        for(auto&j:day[i])
        {
            int u=t[j];
            update(tin[u],-w[j]);
        }
    }
    //ford(u,1,n)
        //cout<<c[u]<<"\n";
    for(auto&u:stt)
    {
        ll s=0;
        for(auto&v:adj[u])
            s+=dp[v];
        if(c[u]!=-inf)
            dp[u]=Maxmize(s,c[u]);
        else
            dp[u]=s;
    }
    cout<<dp[1];
}
void DFS2(int u)
{
    dp[u]=0;
    c[u]=0;
    ump[u].clear();
    for(auto&v:adj[u])
    {
        DFS2(v);
        dp[u]+=Maxmize(dp[v],c[v]);
        if(isz(ump[u])<isz(ump[v]))
        {
            swap(ump[u],ump[v]);
            swap(c[u],c[v]);
        }
        for(auto&[d,w]:ump[v])
        {
            ump[u][d]+=w;
            c[u]=Maxmize(c[u],ump[u][d]);
        }
    }
    for(auto&[d,w]:f[u])
    {
        ump[u][d]+=w;
        c[u]=Maxmize(c[u],ump[u][d]);
    }
}
void khac()
{
    cin>>n>>m>>k;
    ford(i,2,n)
    {
        cin>>p[i];
        adj[p[i]].pb(i);
        //adj[i].pb(p[i]);
    }
    ford(i,1,m)
    {
        cin>>t[i]>>d[i]>>w[i];
        //day[d[i]].pb(i);
        f[t[i]].pb({d[i],w[i]});
    }
    DFS2(1);
    cout<<dp[1];
}
void randd()
{
    cin>>n>>m>>k;
    ford(i,2,n)
    {
        cin>>p[i];
        adj[p[i]].pb(i);
        //adj[i].pb(p[i]);
    }
    ford(i,1,m)
    {
        cin>>t[i]>>d[i]>>w[i];
        //day[d[i]].pb(i);
        f[t[i]].pb({d[i],w[i]});
        dp[1]+=w[i];
    }
    cout<<dp[1];
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //file("fruit");
    khac();
    //randd();
    //nguu();
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17