Submission #434670

#	Time	Username	Problem	Language	Result	Execution time	Memory
434670		Trunkty	Dreaming (IOI13_dreaming)	C++14	100 / 100	211 ms	34660 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<int>> pairs[100005];
bool check[100005];
int mini,diam;
int dp[100005][3];
priority_queue<int> nums;

int dfs(int par, int a, int curr){
    check[a] = true;
    for(vector<int> i:pairs[a]){
        if(i[0]!=par){
            int x = dfs(a,i[0],i[1]);
            if(x>dp[a][1]){
                dp[a][2] = dp[a][1];
                dp[a][1] = x;
            }
            else if(x>dp[a][2]){
                dp[a][2] = x;
            }
        }
    }
    diam = max(diam,dp[a][1]+dp[a][2]);
    return dp[a][1]+curr;
}

void dfs2(int par, int a, int curr){
    if(curr>dp[a][1]){
        dp[a][2] = dp[a][1];
        dp[a][1] = curr;
    }
    else if(curr>dp[a][2]){
        dp[a][2] = curr;
    }
    for(vector<int> i:pairs[a]){
        if(i[0]!=par){
            if(dp[i[0]][1]+i[1]==dp[a][1]){
                dfs2(a,i[0],dp[a][2]+i[1]);
            }
            else{
                dfs2(a,i[0],dp[a][1]+i[1]);
            }
        }
    }
    mini = min(mini,dp[a][1]);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;i++){
        pairs[A[i]].push_back({B[i],T[i]});
        pairs[B[i]].push_back({A[i],T[i]});
    }
    for(int i=0;i<N;i++){
        if(!check[i]){
            mini = 1e9;
            dfs(-1,i,0);
            dfs2(-1,i,0);
            nums.push(mini);
        }
    }
    if(M==N-1){
        return diam;
    }
    else if(M==N-2){
        int a = nums.top();
        nums.pop();
        int b = nums.top();
        return max(a+b+L,diam);    
    }
    else{
        int a = nums.top();
        nums.pop();
        int b = nums.top();
        nums.pop();
        int c = nums.top();
        return max(max(a+b+L,b+c+2*L),diam);
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23