Submission #998719

#	Time	Username	Problem	Language	Result	Execution time	Memory
998719		Muhammet	Dreaming (IOI13_dreaming)	C++17	100 / 100	222 ms	50000 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];

int N1, M, L1, A1[N], B1[N], T1[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);
            // cout << i << ' ' << mn << '\n';
        }
    }

    ll k = 0;
    for(int i = 0; i < n; i++){
        k = max(k,f[i] + p[i].back().ff);
    }

    sort(v1.begin(), v1.end());
    // assert(v1.size() == 2);
    // return v1.back() + l + v1[sz(v1) - 2];
    k = max(v1.back(),k);
    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]);

    // for(int i = 0; i < n; i++) cout << i << ' ' << f[i] << ' ' << p[i].back() << '\n';

    return k;
}

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