Submission #1286269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286269		modwwe	Tree (IOI24_tree)	C++20	0 / 100	76 ms	39816 KiB

tree

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "cc"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e17+7;
const int mod2 =998244353;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
                                                               r2, center;
ll  i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
bool ok[200001];
ll c[200001],par[200001];
vector<int> v[200001];
ll sz[200001],pl[1000014],sr[1000014],dc[1000014];
vector<int> vc;
void ddc(int x)
{
    for(auto f:v[x])ddc(f);
    if(v[x].size()==0)pl[1]++;
    else
    {
        vc.pb(x);
    }
}
struct dsuconcu
{

    int get(int x)
    {
        if(par[x]!=x)par[x]=get(par[x]);
        return par[x];
    }
    void noi(int x,int y)
    {
        y=get(y);
        par[x]=y;
        sz[y]+=sz[x];
    }
} ds;
bool cmp(int x,int y)
{
    return c[x]>c[y];
}
void init(std::vector<int> P, std::vector<int> W)
{
    n=P.size();
    for(int i=1; i<n; i++)
        v[P[i]+1].pb(i+1);
    for(int i=0; i<=n; i++)
        dc[i]=1,par[i]=i,sz[i]=1;
    for(int i=0; i<n; i++)
        c[i]=W[i];
    sort(vc.begin(),vc.end(),cmp);
    ddc(1);
    for(auto x:vc)
    {
        s4=0;
        for(auto f:v[x])
        s4+=sz[ds.get(f)],dem++;
        pl[1]+=(dem-1)*c[x];
        int hihi=P[ds.get(x)-1]+1;
        s4--;
        sr[dc[hihi]]++;
        sr[dc[hihi]+s4]--;
        pl[dc[hihi]+1]+=s4*c[x];
        pl[dc[hihi]+s4+1]-=(dc[hihi]+s4)*c[x];
        dc[hihi]+=s4;
        for(auto f:v[i])ds.noi(f,x);
        sz[ds.get(x)]--;
    }
    for(int i=1; i<=1e6; i++)pl[i]+=pl[i-1];
    for(int i=1e6-1; i>=1; --i)sr[i]+=sr[i+1];
}
long long query(int l,int r)
{
    int k=r/l+1;
    return sr[k]*r+pl[k]*l;
}

Compilation message (stderr)

tree.cpp:26:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   26 | const int inf = 1e17+7;
      |                 ~~~~^~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19