oj.uz

Submission #274118

# Submission time Handle Problem Language Result Execution time Memory
274118 2020-08-19T08:34:56 Z 문홍윤(#5110) Mountains and Valleys (CCO20_day1problem3) C++17
1 / 25
 255 ms 13652 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const int inf=1e9;

int n, m, r1, r2;
vector<int> link[500010];
vector<pair<pii, int> > edg;

struct SEC_MAX{
    int a[2];
    SEC_MAX(){a[0]=a[1]=-inf;}
    void in(int num){
        if(a[1]<=num){
            if(a[0]<=num){
                a[1]=a[0];
                a[0]=num;
            }
            a[1]=num;
        }
    }
    int qu(int num){return a[0]==num?a[1]:a[0];}
};

int dis[500010], sp[500010][30], ans;

void dfs(int num, int par){
    dis[num]=dis[par]+1;
    sp[num][0]=par;
    for(auto i:link[num]){
        if(i==par)continue;
        dfs(i, num);
    }
}
int lca(int x, int y){
    if(dis[x]>dis[y])swap(x, y);
    for(int i=20; i>=0; i--){
        if(dis[y]-dis[x]>=(1<<i))y=sp[y][i];
    }
    if(x==y)return x;
    for(int i=20; i>=0; i--){
        if(sp[x][i]!=sp[y][i]){
            x=sp[x][i];
            y=sp[y][i];
        }
    }
    return sp[x][0];
}
int get_dist(int x, int y){return dis[x]+dis[y]-2*dis[lca(x, y)];}

int dis2[500010], p[500010];
void dfs2(int num, int par){
    dis2[num]=dis2[par]+1;
    p[num]=par;
    for(auto i:link[num]){
        if(i==par)continue;
        dfs2(i, num);
    }
}

vector<SEC_MAX> rt1, rt2;
int h[500010], th[500010];
bool ch[500010];
void dfs4(int num, int par, int val){
    th[num]=val;
    for(auto i:link[num]){
        if(i==par)continue;
        dfs4(i, num, val);
    }
}
void dfs3(int num, int par){
    SEC_MAX scmx;
    scmx.in(0);
    for(auto i:link[num]){
        if(i==par||ch[i])continue;
        dfs3(i, num);
        h[num]=max(h[num], h[i]+1);
    }
    if(ch[num])rt1.eb(scmx);
    int nw=rt1.size()-1;
    for(auto i:link[num]){
        if(i==par)continue;
        if(ch[i])dfs3(i, num);
        else if(ch[num]){
            rt1[nw].in(h[i]+1);
            dfs4(i, num, h[i]+1);
        }
    }
}
int pfmax[500010], sfmax[500010];
int query(int a, int b, int c, int d, int d1, int d2, int h1, int h2){
    int ret=0;
    pfmax[a]=d1-h1;
    for(int i=a+1; i<b; i++)pfmax[i]=max(pfmax[i-1], rt1[i].qu(-1)+i-a);
    sfmax[b]=d2-h2;
    for(int i=b-1; i>a; i--)sfmax[i]=max(sfmax[i+1], rt2[i].qu(-1)+b-i);
    for(int i=a; i<b; i++)ret=max(ret, pfmax[i]+sfmax[i+1]+2);
    for(int i=a+1; i<b; i++)ret=max(ret, rt1[i].qu(-1)+rt1[i].qu(rt1[i].qu(-1))+b-a);
    ret=max(ret, b+rt1[a].qu(th[c]));
    ret=max(ret, dis2[r2]-1-a+rt1[b].qu(th[d]));
    for(int i=a; i<=b; i++)pfmax[i]=sfmax[i]=0;
    return ret+h1+h2;
}
int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a++; b++;
        if(c==1){
            link[a].eb(b);
            link[b].eb(a);
        }
        else edg.eb(mp(a, b), c);
    }
    dfs(1, 0);
    for(int j=1; j<=20; j++){
        for(int i=1; i<=n; i++)sp[i][j]=sp[sp[i][j-1]][j-1];
    }
    dfs2(1, 0);
    r1=max_element(dis2+1, dis2+n+1)-dis2;
    dfs2(r1, 0);
    r2=max_element(dis2+1, dis2+n+1)-dis2;
    int tmp=r2;
    while(tmp){
        ch[tmp]=true;
        tmp=p[tmp];
    }
    dfs3(r1, 0);
    rt2=rt1;
    //for(int i=0; i<dis2[r2]; i++)rt1[i]+=i, rt2[i]+=dis2[r2]-1-i;
    //for(int i=1; i<dis2[r2]; i++)rt1[i]=max(rt1[i], rt1[i-1]);
    //for(int i=dis2[r2]-2; i>=0; i--)rt2[i]=max(rt2[i], rt2[i+1]);
    //for(int i=0; i<dis2[r2]-1; i++)seg.update(1, 0, dis2[r2]-2, i, rt1[i]+rt2[i+1]);
    ans=2*(n-1)-dis2[r2]+1;
    for(auto i:edg){
        int d=get_dist(i.F.F, i.F.S);
        if(d<=i.S)continue;
        int nd=2*(n-1)+i.S;
        int r1to1=get_dist(r1, i.F.F)+dis2[r2]-1-get_dist(r2, i.F.F);
        int r1to2=get_dist(r1, i.F.S)+dis2[r2]-1-get_dist(r2, i.F.S);
        r1to1/=2, r1to2/=2;
        if(r1to1>r1to2)swap(i.F.F, i.F.S);
        int d1=get_dist(r1, i.F.F);
        int d2=get_dist(r2, i.F.S);
        int h1=d1+get_dist(r2, i.F.F)-dis2[r2]+1;
        int h2=d2+get_dist(r1, i.F.S)-dis2[r2]+1;
        h1/=2; h2/=2;
        int mk1=d1-h1;
        int mk2=dis2[r2]-1-d2+h2;
        ans=min(ans, nd-query(mk1, mk2, i.F.F, i.F.S, d1, d2, h1, h2));
    }
    printf("%d", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 9 ms 12160 KB Output is correct
17 Correct 10 ms 12080 KB Output is correct
18 Correct 9 ms 12104 KB Output is correct
19 Correct 8 ms 12160 KB Output is correct
20 Correct 8 ms 12160 KB Output is correct
21 Incorrect 9 ms 12160 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 13648 KB Output is correct
2 Correct 255 ms 13652 KB Output is correct
3 Incorrect 146 ms 13560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 9 ms 12160 KB Output is correct
17 Correct 10 ms 12080 KB Output is correct
18 Correct 9 ms 12104 KB Output is correct
19 Correct 8 ms 12160 KB Output is correct
20 Correct 8 ms 12160 KB Output is correct
21 Incorrect 9 ms 12160 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 9 ms 12160 KB Output is correct
17 Correct 10 ms 12080 KB Output is correct
18 Correct 9 ms 12104 KB Output is correct
19 Correct 8 ms 12160 KB Output is correct
20 Correct 8 ms 12160 KB Output is correct
21 Incorrect 9 ms 12160 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 9 ms 12160 KB Output is correct
17 Correct 10 ms 12080 KB Output is correct
18 Correct 9 ms 12104 KB Output is correct
19 Correct 8 ms 12160 KB Output is correct
20 Correct 8 ms 12160 KB Output is correct
21 Incorrect 9 ms 12160 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 9 ms 12160 KB Output is correct
17 Correct 10 ms 12080 KB Output is correct
18 Correct 9 ms 12104 KB Output is correct
19 Correct 8 ms 12160 KB Output is correct
20 Correct 8 ms 12160 KB Output is correct
21 Incorrect 9 ms 12160 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 9 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 8 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 9 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 8 ms 12160 KB Output is correct
12 Correct 9 ms 12160 KB Output is correct
13 Correct 11 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 8 ms 12160 KB Output is correct
16 Correct 9 ms 12160 KB Output is correct
17 Correct 10 ms 12080 KB Output is correct
18 Correct 9 ms 12104 KB Output is correct
19 Correct 8 ms 12160 KB Output is correct
20 Correct 8 ms 12160 KB Output is correct
21 Incorrect 9 ms 12160 KB Output isn't correct
22 Halted 0 ms 0 KB -