Submission #1003026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003026		tamir1	Dreaming (IOI13_dreaming)	C++17	18 / 100	173 ms	38996 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
 
#define N 200005
#define ff first
#define sz(s) (int)s.size()
#define ss second
#define ll long long
 
vector <pair<ll,ll>> v[N], p[N];
 
vector <ll> v1;
 
map <ll,bool> vis, vi;
 
ll mn, f[N];
 
ll dfs(ll x){
    vis[x] = 1;
    for(auto i : v[x]){
        if(vis[i.ff] == 0){
            p[x].push_back({dfs(i.ff) + i.ss, i.ff});
        }
    }
    p[x].push_back({0,-1});
    sort(p[x].begin(), p[x].end());
    return p[x].back().ff;
}
 
void df(ll x){
    vi[x] = 1;
    mn = min(mn,max(p[x].back().ff,f[x]));
    for(auto i : v[x]){
        if(vi[i.ff] == 0){
            ll y = p[x].back().ff;
            if(p[x].back().ss == i.ff) y = p[x][sz(p[x]) - 2].ff;
            f[i.ff] = (max(y,f[x]) + i.ss);
        }
    }
    for(auto i : v[x]){
        if(vi[i.ff] == 0) df(i.ff);
    }
    return;
}
 
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    vis.clear();
    v1.clear();
    vi.clear();
    for(int i = 0; i < n; i++){
        v[i].clear();
        p[i].clear();
        f[i] = 0;
    }
 
    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]});
    }
 
    for(int i = 0; i < n; i++){
        if(vis[i] == 0){
            dfs(i);
            mn = INT_MAX;
            df(i);
            v1.push_back(mn);
        }
    }
    sort(v1.begin(), v1.end());
    ll k = v1.back();
    if(sz(v1) >= 2) k = max(k,v1.back() + l + v1[sz(v1) - 2]);
    if(sz(v1) >= 3) k = max(k, v1[sz(v1) - 3] + l*2 + v1[sz(v1) - 2]);
    return k;
}

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