oj.uz

Submission #274340

# Submission time Handle Problem Language Result Execution time Memory
274340 2020-08-19T11:08:59 Z gs18115 Mountains and Valleys (CCO20_day1problem3) C++14
3 / 25
 37 ms 40320 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct max3
{
    int a,b,c;
    max3(){a=b=c=0;}
    inline void upd(int x)
    {
        if(x>a)
            c=b,b=a,a=x;
        else if(x>b)
            c=b,b=x;
        else if(x>c)
            c=x;
        return;
    }
    inline int get()
    {
        return a;
    }
    inline int get(int x)
    {
        return x==a?b:a;
    }
    inline int get(int x,int y)
    {
        if(x<y)
            swap(x,y);
        return x==a?(y==b?c:b):(y==a?b:a);
    }
};
struct max4
{
    int a,b,c,d;
    max4(){a=b=c=d=0;}
    inline void upd(int x)
    {
        if(x>a)
            d=c,c=b,b=a,a=x;
        else if(x>b)
            d=c,c=b,b=x;
        else if(x>c)
            d=c,c=x;
        else if(x>d)
            d=x;
        return;
    }
    inline int get()
    {
        return a;
    }
    inline int get(int x)
    {
        return x==a?b:a;
    }
    inline int get(int x,int y)
    {
        if(x<y)
            swap(x,y);
        return x==a?(y==b?c:b):(y==a?b:a);
    }
};
vector<int>adj[500010];
int depth[500010];
void ddfs(int x,int p)
{
    depth[x]=depth[p]+1;
    for(int&t:adj[x])
        if(t!=p)
            ddfs(t,x);
    return;
}
int dep[500010];
int spa[500010][19];
inline int kpa(int x,int k)
{
    for(;k>0;k^=k&-k)
        x=spa[x][__builtin_ctz(k)];
    return x;
}
inline int lca(int x,int y)
{
    if(dep[x]>dep[y])
        x=kpa(x,dep[x]-dep[y]);
    else
        y=kpa(y,dep[y]-dep[x]);
    if(x==y)
        return x;
    for(int i=19;i-->0;)
        if(spa[x][i]!=spa[y][i])
            x=spa[x][i],y=spa[y][i];
    return spa[x][0];
}
max3 dp1[500010],dp2[500010];
int dpex[500010],dpe[500010];
int spd[500010][19];
int cm[500010][19];
pi cut[500010][19];
inline pair<pi,pi>pth(int x,int k)
{
    int ret=max({dp2[x].a,dp1[x].a+dp1[x].b});
    pi ret2(dp1[x].a,-inf);
    int len=0;
    while(k>0)
    {
        int i=__builtin_ctz(k);
        k^=k&-k;
        //ret=max(ret,spd[x][i]);
        ret2.se=max({cm[x][i]+len,ret2.se+(1<<i),ret2.fi+cut[x][i].se});
        if(cut[x][i].fi+len>ret2.fi)
            ret2.fi=cut[x][i].fi+len;
        len+=1<<i;
        x=spa[x][i];
    }
    return pair<pi,pi>(pi(ret,x),ret2);
}
max4 dp3[500010];
max3 dp4[500010];
void sdfs(int x,int p)
{
    spa[x][0]=p;
    for(int i=0;i<18;i++)
        spa[x][i+1]=spa[spa[x][i]][i];
    dep[x]=dep[p]+1;
    for(int&t:adj[x])
        if(t!=p)
            sdfs(t,x),dp1[x].upd(dp1[t].a+1),
            dp2[x].upd(max(dp2[t].a,dp1[t].a+dp1[t].b));
    dp3[x].a=dp1[x].a;
    dp3[x].b=dp1[x].b;
    dp3[x].c=dp1[x].c;
    dp4[x]=dp2[x];
    return;
}
void dfs2(int x,int p)
{
    spd[x][0]=dpex[x];
    cm[x][0]=dpe[x];
    cut[x][0].fi=dpe[x]+1;
    cut[x][0].se=dpe[x];
    for(int i=0,y=x;i<18;y=spa[y][i++])
    {
        if(spa[x][i]==0)
            break;
        spd[x][i+1]=max(spd[x][i],spd[spa[x][i]][i]);
        cm[x][i+1]=max({cm[x][i]+(1<<i),cm[spa[x][i]][i]+(1<<i),
        cut[x][i].fi+cut[spa[x][i]][i].se});
        cut[x][i+1].fi=max(cut[x][i].fi,cut[spa[x][i]][i].fi+(1<<i));
        cut[x][i+1].se=max(cut[spa[x][i]][i].se,cut[x][i].se+(1<<i));
    }
    for(int&t:adj[x])
    {
        if(t!=p)
        {
            int fc1=dp1[t].a+1;
            int fc2=max(dp2[t].a,dp1[t].a+dp1[t].get(dp1[t].a));
            dpex[t]=max(dp2[x].get(fc2),dp1[x].get(fc1)+dp1[x].get(dp1[x].get(fc1),fc1));
            dpe[t]=dp1[x].get(dp1[t].a+1);
            int mx=dp3[x].get(dp1[t].a+1);
            dp3[t].upd(mx+1);
            int mx2=dp3[x].get(mx,dp1[t].a+1);
            int td2=max(dp2[t].a,dp1[t].a+dp1[t].b);
            dp4[t].upd(max(dp4[x].get(td2),mx+mx2));
            dfs2(t,x);
        }
    }
    return;
}
const int bufsiz=1<<20;
char buf[bufsiz+10];
int bcnt;
inline int getint()
{
    int a=0;
    while(buf[bcnt]<'0'||buf[bcnt]>'9')
    {
        bcnt++;
        if(bcnt==bufsiz)
        {
            fread(buf,1,bufsiz,stdin);
            bcnt=0;
        }
    }
    while(buf[bcnt]>='0'&&buf[bcnt]<='9')
    {
        a=a*10+buf[bcnt]-'0';
        bcnt++;
        if(bcnt==bufsiz)
        {
            fread(buf,1,bufsiz,stdin);
            bcnt=0;
        }
    }
    return a;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fread(buf,1,bufsiz,stdin);
    int n,m;
    n=getint(),m=getint();
    vector<pair<pi,int> >ev;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        u=getint(),v=getint(),w=getint();
        u++,v++;
        if(w==1)
            adj[u].eb(v),adj[v].eb(u);
        else if(w*2<n)
            ev.eb(pi(u,v),w);
    }
    sdfs(1,0);
    int ans=inf;
    {
        int d1=max_element(dep+1,dep+n+1)-dep;
        ddfs(d1,0);
        ans=2*n-1-*max_element(depth+1,depth+n+1);
    }
    dfs2(1,0);
    for(auto&t:ev)
    {
        int u=t.fi.fi;
        int v=t.fi.se;
        int w=t.se;
        int l=lca(u,v);
        int len=dep[u]+dep[v]-dep[l]*2;
        int dmax=0,cmax=0;
        if(v==l)
            swap(u,v);
        if(u==l)
        {
            auto qq=pth(v,dep[v]-dep[l]-1);
            auto q1=qq.fi.fi;
            auto q2=qq.se;
            int y=qq.fi.se;
            q2.se++;
            /*{
                int fc1=dp1[y].a+1;
                int fc2=max(dp2[y].a,dp1[y].a+dp1[y].get(dp1[y].a));
                int get1=0,get2=0;
                {
                    if(fc1==dp3[l].a)
                        get1=dp3[l].b,get2=dp3[l].c;
                    else
                    {
                        get1=dp3[l].a;
                        if(fc1==dp3[l].b)
                            get2=dp3[l].c;
                        else
                            get2=dp3[l].b;
                    }
                }
                dmax=max({q1,dp4[l].get(fc2),get1+get2});
            }*/
            {
                int cur=dp3[l].get(dp1[y].a+1);
                cmax=max(q2.se,q2.fi+cur);
            }
        }
        else
        {
            auto qqu=pth(u,dep[u]-dep[l]-1);
            auto qqv=pth(v,dep[v]-dep[l]-1);
            int qu1=qqu.fi.fi;
            int qv1=qqv.fi.fi;
            auto qu2=qqu.se;
            auto qv2=qqv.se;
            int yu=qqu.fi.se;
            int yv=qqv.fi.se;
            qu2.se++,qv2.se++;
            /*{
                int fcu1=dp1[yu].a+1;
                int fcv1=dp1[yv].a+1;
                int fcu2=max(dp2[yu].a,dp1[yu].a+dp1[yu].b);
                int fcv2=max(dp2[yv].a,dp1[yv].a+dp1[yv].b);
                int get1=0,get2=0;
                {
                    int mx=max(fcu1,fcv1),mn=min(fcu1,fcv1);
                    if(mx==dp3[l].a)
                    {
                        if(mn==dp3[l].b)
                            get1=dp3[l].c,get2=dp3[l].d;
                        else if(mn==dp3[l].c)
                            get1=dp3[l].b,get2=dp3[l].d;
                        else
                            get1=dp3[l].b,get2=dp3[l].c;
                    }
                    else if(mn==dp3[l].a)
                        get1=dp3[l].b,get2=dp3[l].c;
                    else
                    {
                        get1=dp3[l].a;
                        if(mx==dp3[l].b)
                        {
                            if(mn==dp3[l].c)
                                get2=dp3[l].d;
                            else
                                get2=dp3[l].c;
                        }
                        else
                            get2=dp3[l].b;
                    }
                }
                dmax=max({qu1,qv1,dp4[l].get(fcu2,fcv2),get1+get2});
            }*/
            {
                int cur=dp3[l].get(dp1[yu].a+1,dp1[yv].a+1);
                cmax=max({qu2.se+(dep[v]-dep[l]),qv2.se+(dep[u]-dep[l]),qu2.fi+qv2.fi,
                qu2.fi+cur+(dep[v]-dep[l]),qv2.fi+cur+(dep[u]-dep[l])});
            }
        }
        ans=min(ans,n*2-2-dmax-len+w);
        ans=min(ans,n*2-4-cmax+w);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:247:18: warning: unused variable 'q1' [-Wunused-variable]
  247 |             auto q1=qq.fi.fi;
      |                  ^~
Main.cpp:278:17: warning: unused variable 'qu1' [-Wunused-variable]
  278 |             int qu1=qqu.fi.fi;
      |                 ^~~
Main.cpp:279:17: warning: unused variable 'qv1' [-Wunused-variable]
  279 |             int qv1=qqv.fi.fi;
      |                 ^~~
Main.cpp:212:10: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  212 |     fread(buf,1,bufsiz,stdin);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int getint()':
Main.cpp:192:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  192 |             fread(buf,1,bufsiz,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:202:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  202 |             fread(buf,1,bufsiz,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct
16 Correct 27 ms 37536 KB Output is correct
17 Correct 26 ms 37624 KB Output is correct
18 Incorrect 23 ms 37632 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 40192 KB Output is correct
2 Correct 27 ms 40320 KB Output is correct
3 Correct 37 ms 40064 KB Output is correct
4 Correct 28 ms 40064 KB Output is correct
5 Correct 32 ms 39936 KB Output is correct
6 Correct 27 ms 39808 KB Output is correct
7 Correct 27 ms 40320 KB Output is correct
8 Correct 27 ms 40056 KB Output is correct
9 Correct 33 ms 40320 KB Output is correct
10 Correct 27 ms 39936 KB Output is correct
11 Correct 33 ms 40192 KB Output is correct
12 Correct 27 ms 39936 KB Output is correct
13 Correct 27 ms 40064 KB Output is correct
14 Correct 29 ms 40064 KB Output is correct

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct
16 Correct 27 ms 37536 KB Output is correct
17 Correct 26 ms 37624 KB Output is correct
18 Incorrect 23 ms 37632 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct
16 Correct 27 ms 37536 KB Output is correct
17 Correct 26 ms 37624 KB Output is correct
18 Incorrect 23 ms 37632 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct
16 Correct 27 ms 37536 KB Output is correct
17 Correct 26 ms 37624 KB Output is correct
18 Incorrect 23 ms 37632 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct
16 Correct 27 ms 37536 KB Output is correct
17 Correct 26 ms 37624 KB Output is correct
18 Incorrect 23 ms 37632 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 37632 KB Output is correct
2 Correct 25 ms 37632 KB Output is correct
3 Correct 25 ms 37632 KB Output is correct
4 Correct 24 ms 37632 KB Output is correct
5 Correct 28 ms 37624 KB Output is correct
6 Correct 25 ms 37632 KB Output is correct
7 Correct 24 ms 37632 KB Output is correct
8 Correct 29 ms 37632 KB Output is correct
9 Correct 24 ms 37632 KB Output is correct
10 Correct 26 ms 37664 KB Output is correct
11 Correct 24 ms 37632 KB Output is correct
12 Correct 24 ms 37632 KB Output is correct
13 Correct 27 ms 37632 KB Output is correct
14 Correct 26 ms 37632 KB Output is correct
15 Correct 32 ms 37624 KB Output is correct
16 Correct 27 ms 37536 KB Output is correct
17 Correct 26 ms 37624 KB Output is correct
18 Incorrect 23 ms 37632 KB Output isn't correct
19 Halted 0 ms 0 KB -