Submission #586482

#	Time	Username	Problem	Language	Result	Execution time	Memory
586482		FatihSolak	Dreaming (IOI13_dreaming)	C++17	100 / 100	102 ms	32616 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<pair<int,int>> adj[N];
int maxdep[N];
int dep[N];
bool vis[N];
void dfs(int v,int par){
    vis[v] = 1;
    for(auto u:adj[v]){
        if(u.first == par)continue;
        dep[u.first] = dep[v] + u.second;
        dfs(u.first,v);
        maxdep[v] = max(maxdep[v],maxdep[u.first] + u.second);
    }
}
int mini,ans = 0;
void dfs1(int v,int par,int c){
    vis[v] = 1;
    multiset<int> s = {0};
    for(auto u:adj[v]){
        if(u.first == par)continue;
        s.insert(maxdep[u.first] + u.second);
    }
    for(auto u:adj[v]){
        if(u.first == par)continue;
        s.erase(s.find(maxdep[u.first] + u.second));
        dfs1(u.first,v,max(c,*s.rbegin()) + u.second);
        s.insert(maxdep[u.first] + u.second);
    }
    ans = max(ans,max(c,maxdep[v]));
    mini = min(mini,max(c,maxdep[v]));
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i = 0;i<m;i++){
        a[i]++,b[i]++;
        adj[a[i]].push_back({b[i],t[i]});
        adj[b[i]].push_back({a[i],t[i]});
    }
    vector<int> v;
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            dfs(i,0);
        }
    }
    for(int i = 1;i<=n;i++){
        vis[i] = 0;
    }
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            mini = 1e9;
            dfs1(i,0,0);
            v.push_back(mini);
        }
    }
    sort(v.begin(),v.end());
    for(int i = v.size()-2;i>=0;i--){
        ans = max(ans,v[i] + v[v.size() - 1] + l);
        v[v.size()-1] = max(v[v.size()-1],v[i] + l);
    }
    return ans;
}

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