oj.uz

Submission #970545

# Submission time Handle Problem Language Result Execution time Memory
970545 2024-04-26T17:09:16 Z yeediot Dreaming (IOI13_dreaming) C++17
0 / 100
 38 ms 14928 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define F first
#define S second
#define chmin(a,b) a=(a<b?a:b)
#define chmax(a,b) a=(a>b?a:b)
const int mxn=1e5+5;
vector<pair<int,int>>adj[mxn];
pair<int,int>dp[mxn];
bool vis[mxn];
int dp2[mxn];
void dfs(int v,int pa){
    vis[v]=1;
    for(auto [u,len]:adj[v]){
        if(u==pa)
            continue;
        dfs(u,v);
        if(dp[v].F<=dp[u].F+len){
            dp[v].S=dp[v].F;
            dp[v].F=dp[u].F+len;
        }
        else if(dp[v].S<dp[u].F+len){
            dp[v].S=dp[u].F+len;
        }
    }
}
pair<int,int> mn;
int mx=-2e9;
void reroot(int v,int pa){
    chmin(mn,make_pair(dp[v].F,v));
    for(auto [u,len]:adj[v]){
        if(u==pa)
            continue;
        int x;
        if(dp[v].F!=dp[u].F+len){
            x=dp[v].F;
        }
        else{
            x=dp[v].S;
        }
        x+=len;
        if(dp[u].F<=x){
            dp[u].S=dp[u].F;
            dp[u].F=x;
        }
        else if(dp[u].S<x){
            dp[u].S=x;
        }
        reroot(u,v);
    }
}
void dfs2(int v,int pa){
    for(auto [u,len]:adj[v]){
        if(u==pa)
            continue;
        dfs2(u,v);
        chmax(mx,dp2[v]+dp2[u]+len);
        chmax(dp2[v],dp2[u]+len);
    }
}
vector<pair<int,int>>v;
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
    for(int i=0;i<m;i++){
        adj[a[i]].push_back({b[i],t[i]});
        adj[b[i]].push_back({a[i],t[i]});
    }
    for(int i=1;i<=n;i++){
        if(vis[i])
            continue;
        mn={2e9,2e9};
        dfs(i,i);
        reroot(i,i);
        v.push_back(mn);
    }
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    for(int i=1;i<(int)v.size();i++){
        adj[v[0].S].push_back({v[i].S,l});
        adj[v[i].S].push_back({v[0].S,l});
    }
    dfs2(1,1);
    return mx;
}
#ifdef local
int main(){
    freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);
    int n,m,l;
    cin>>n>>m>>l;
    int a[m],b[m],t[m];
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>t[i];
    }
    cout<<travelTime(n,m,l,a,b,t)<<'\n';
}
#else
#endif

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13940 KB Output is correct
2 Correct 34 ms 14928 KB Output is correct
3 Correct 22 ms 9860 KB Output is correct
4 Correct 5 ms 5976 KB Output is correct
5 Correct 5 ms 5464 KB Output is correct
6 Correct 10 ms 7004 KB Output is correct
7 Incorrect 1 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 4968 KB Output is correct
3 Incorrect 1 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13940 KB Output is correct
2 Correct 34 ms 14928 KB Output is correct
3 Correct 22 ms 9860 KB Output is correct
4 Correct 5 ms 5976 KB Output is correct
5 Correct 5 ms 5464 KB Output is correct
6 Correct 10 ms 7004 KB Output is correct
7 Incorrect 1 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9100 KB Output is correct
2 Correct 20 ms 9080 KB Output is correct
3 Correct 19 ms 8848 KB Output is correct
4 Correct 22 ms 8984 KB Output is correct
5 Correct 23 ms 9356 KB Output is correct
6 Correct 21 ms 9944 KB Output is correct
7 Correct 21 ms 9048 KB Output is correct
8 Correct 19 ms 8980 KB Output is correct
9 Correct 19 ms 9004 KB Output is correct
10 Correct 25 ms 9456 KB Output is correct
11 Correct 1 ms 4956 KB Output is correct
12 Correct 11 ms 9768 KB Output is correct
13 Correct 11 ms 9680 KB Output is correct
14 Correct 11 ms 9676 KB Output is correct
15 Correct 11 ms 9676 KB Output is correct
16 Correct 10 ms 9680 KB Output is correct
17 Correct 10 ms 9756 KB Output is correct
18 Correct 17 ms 9680 KB Output is correct
19 Correct 11 ms 9680 KB Output is correct
20 Incorrect 1 ms 4952 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 4968 KB Output is correct
3 Incorrect 1 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13940 KB Output is correct
2 Correct 34 ms 14928 KB Output is correct
3 Correct 22 ms 9860 KB Output is correct
4 Correct 5 ms 5976 KB Output is correct
5 Correct 5 ms 5464 KB Output is correct
6 Correct 10 ms 7004 KB Output is correct
7 Incorrect 1 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -