Submission #997931

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

vector <ll> p[N], v1;

map <ll,bool> vis, vi;

ll mn;

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);
        }
    }
    p[x].push_back(0);
    sort(p[x].begin(), p[x].end());
    return p[x].back();
}

void df(ll x){
    vi[x] = 1;
    mn = min(mn,p[x].back());
    for(auto i : v[x]){
        if(vi[i.ff] == 0){
            ll y = p[x].back();
            if(y == p[i.ff].back() + i.ss) y = p[x][sz(p[x]) - 2];
            p[i.ff].push_back(y + i.ss);
            sort(p[i.ff].begin(), p[i.ff].end());
            df(i.ff);
        }
    }
    return;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    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 = 1e9;
            df(i);
            v1.push_back(mn);
        }
    }

    sort(v1.begin(), v1.end());

    ll k = v1[sz(v1) - 1] + 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: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23