oj.uz

Submission #273553

# Submission time Handle Problem Language Result Execution time Memory
273553 2020-08-19T05:51:24 Z 문홍윤(#5110) Mountains and Valleys (CCO20_day1problem3) C++17
0 / 25
 33 ms 26468 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;
vector<int> link[500010];
vector<pair<pii, int> > edg;

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];
void dfs2(int num, int par){
    dis2[num]=dis2[par]+1;
    for(auto i:link[num]){
        if(i==par)continue;
        dfs2(i, num);
    }
}

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);
    int r1=max_element(dis2+1, dis2+n+1)-dis2;
    dfs2(r1, 0);
    int r2=max_element(dis2+1, dis2+n+1)-dis2;
    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-2)+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);
        if(r1to1>r1to2){
            swap(i.F.F, i.F.S);
            swap(r1to1, r1to2);
        }
        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;
        int mk1=d1;
        int mk2=d-d2;
        if(mk1>=mk2||mk1>=d-h2||mk2<=h1)ans=min(ans, nd-d1-d2);
        else assert(0);
        //else ans=min(ans, nd-(mk1-r1to1)+(r1to2-mk2+h2)+1);
    }
    printf("%d", ans);
}

Compilation message

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

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 26468 KB Execution killed with signal 11
2 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 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 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 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 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 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 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 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 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 Runtime error 26 ms 24320 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -