Submission #850234

#	Time	Username	Problem	Language	Result	Execution time	Memory
850234		Tai_xiu	Putovanje (COCI20_putovanje)	C++14	110 / 110	134 ms	24544 KiB

putovanje

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200001;
ll bit1[200001],bit2[200001];
unsigned int s[maxn],d_hld[maxn],cl[maxn],pos[maxn],id=0,head[maxn],pd[maxn],n,e_pre[maxn];
struct item
{
    int v,t1,t2;
};
vector<item>g[maxn];
void dfs(int u)
{
    cl[u]=1;
    s[u]=1;
    int smax=0,imax=0;
    for (int i=0;i<g[u].size();i++){
        int v=g[u][i].v;
        if (cl[v]==0){
            pd[v]=u;
            dfs(v);
            s[u]+=s[v];
            if (smax<s[v]){
                smax=s[v];
                imax=i;
            }
        }
    }
    swap(g[u][0],g[u][imax]);
}
void hld(int u)
{
    pos[u]=++id;
    for (item &i:g[u]){
        int v=i.v;
        if (pd[v]==u){
            if (2*s[v]>=s[u]) head[v]=head[u],d_hld[v]=d_hld[u];
            else head[v]=v,d_hld[v]=d_hld[u]+1;
            hld(v);
        }
    }
}
void update1(int i,ll v)
{
    while (i<=n){
        bit1[i]+=v;
        i+=(i&-i);
    }
}
void update2(int i,ll v)
{
    while (i<=n){
        bit2[i]+=v;
        i+=(i&-i);
    }
}
ll query1(int i)
{
    ll ans=0;
    while (i>0){
        ans+=bit1[i];
        i&=(i-1);
    }
    return ans;
}
ll query2(int i)
{
    ll ans=0;
    while (i>0){
        ans+=bit2[i];
        i&=(i-1);
    }
    return ans;
}
void updaterange(int l,int r,int v)
{
    update1(l,(n-l+1)*v);
    update1(r+1,-(n-r)*v);
    update2(l,v);
    update2(r+1,-v);
}
ll prefixsum(int i)
{
    return (ll)query1(i)-query2(i)*(n-i);
}
ll rangesum(int l,int r)
{
    return prefixsum(r)-prefixsum(l-1);
}
void mov(int u,int v)
{
    while (d_hld[u]>d_hld[v]){
             //cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
        updaterange(pos[head[u]]+1,pos[u],1);
        u=head[u];
        e_pre[u]++;
        u=pd[u];
    }
    while (d_hld[v]>d_hld[u]){
       //  cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
        updaterange(pos[head[v]]+1,pos[v],1);
        v=head[v];
        e_pre[v]++;
        v=pd[v];
    }
    while (head[u]!=head[v]){
        // cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
        updaterange(pos[head[u]]+1,pos[u],1);
        u=head[u];
        e_pre[u]++;
        u=pd[u];
        updaterange(pos[head[v]]+1,pos[v],1);
        v=head[v];
        e_pre[v]++;
        v=pd[v];
    }
    if (pos[u]<pos[v])
        updaterange(pos[u]+1,pos[v],1);
    else
        updaterange(pos[v]+1,pos[u],1);
}
unsigned int query(int u,int v)
{

    unsigned int kq=0;
    while (d_hld[u]>d_hld[v]){
            //  cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
        kq+=rangesum(pos[head[u]]+1,pos[u]);
        u=head[u];
        kq+=e_pre[u];
        u=pd[u];

    }
      while (d_hld[u]<d_hld[v]){
           //  cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
        kq+=rangesum(pos[head[v]]+1,pos[v]);
        v=head[v];
        kq+=e_pre[v];
        v=pd[v];

    }
    while (head[u]!=head[v]){
       // cout<<pos[head[u]]<<" "<<pos[head[v]]<<endl;
        kq+=rangesum(pos[head[u]]+1,pos[u]);
        u=head[u];
        kq+=e_pre[u];
        u=pd[u];
        kq+=rangesum(pos[head[v]]+1,pos[v]);
        v=head[v];
        kq+=e_pre[v];
        v=pd[v];
    }
    if (pos[u]<pos[v])
        kq+=rangesum(pos[u]+1,pos[v]);
    else
        kq+=rangesum(pos[v]+1,pos[u]);
    return kq;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    int a,b,c,d;
    for (int i=1;i<n;i++){
        cin>>a>>b>>c>>d;
        g[a].push_back({b,c,d});
        g[b].push_back({a,c,d});
    }
    dfs(1);
    hld(1);
    //cout<<1<<endl;
    for (int i=1;i<n;i++)
        mov(i,i+1);
    //cout<<1<<endl;
    long long s=0;
    for (int i=1;i<=n;i++){
        for (item j:g[i]){
            s+=min((long long )query(i,j.v)*j.t1, (long long)j.t2);
        }
    }
    cout<<(long long)s/2;

}

Compilation message (stderr)

putovanje.cpp: In function 'void dfs(int)':
putovanje.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0;i<g[u].size();i++){
      |                  ~^~~~~~~~~~~~
putovanje.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   23 |             if (smax<s[v]){
      |                 ~~~~^~~~~
putovanje.cpp: In function 'void hld(int)':
putovanje.cpp:36:18: warning: comparison of integer expressions of different signedness: 'unsigned int' and 'int' [-Wsign-compare]
   36 |         if (pd[v]==u){
      |             ~~~~~^~~
putovanje.cpp: In function 'void update1(int, long long int)':
putovanje.cpp:45:13: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   45 |     while (i<=n){
      |            ~^~~
putovanje.cpp: In function 'void update2(int, long long int)':
putovanje.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   52 |     while (i<=n){
      |            ~^~~
putovanje.cpp: In function 'int main()':
putovanje.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
  166 |     for (int i=1;i<n;i++){
      |                  ~^~
putovanje.cpp:174:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
  174 |     for (int i=1;i<n;i++)
      |                  ~^~
putovanje.cpp:178:19: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
  178 |     for (int i=1;i<=n;i++){
      |                  ~^~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65