Submission #1007237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007237		Mardonbekhazratov	Dreaming (IOI13_dreaming)	C++17	0 / 100	36 ms	16980 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int n,m,l;
vector<int>sz;
vector<bool>vis;
vector<vector<pair<int,int>>>v;

int dfs(int x){
    vis[x]=true;
    sz[x]=0;
    for(auto [z,w]:v[x]){
        if(!vis[z]){
            sz[x]=max(sz[x],dfs(z)+w);
        }
    }
    return sz[x];
}

int mn;

void dfs2(int x,int y=0){
    vis[x]=true;
    multiset<int>s;
    s.insert(y);
    for(auto [z,w]:v[x]){
        if(!vis[z]){
            s.insert(sz[z]+w);
        }
    }
    mn=min(mn,*s.rbegin());
    for(auto [z,w]:v[x]){
        if(!vis[z]){
            s.erase(s.find(sz[z]+w));
            dfs2(z,*s.rbegin()+w);
            s.insert(sz[z]+w);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    l=L;
    v.assign(n,{});
    for(int i=0;i<m;i++){
        v[A[i]].push_back({B[i],T[i]});
        v[B[i]].push_back({A[i],T[i]});
    }
    sz.resize(n);
    vis.assign(n,false);
    for(int i=0;i<n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    vector<int>a;
    vis.assign(n,false);
    for(int i=0;i<n;i++){
        if(!vis[i]){
            mn=(int)1e9;
            dfs2(i);
            a.push_back(mn);
        }
    }
    if(a.size()==1){
        ;
    }
    sort(a.begin(),a.end());
    return a[a.size()-1]+a[a.size()-2]+l;
}

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