Submission #624532

#	Time	Username	Problem	Language	Result	Execution time	Memory
624532		DAleksa	Dreaming (IOI13_dreaming)	C++17	100 / 100	113 ms	16532 KiB

dreaming

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

using namespace std;

struct edge {
    int v;
    int w;
};

const int N = 1e5 + 10;
vector<edge> g[N];
bool mark[N];
int dist[N];
vector<int> component;
int tin[N], tout[N], timer;
int mn;

void dfs(int u) {
    if(mark[u]) return;
    component.push_back(u);
    mark[u] = true;
    for(auto v : g[u]) {
        if(mark[v.v]) continue;
        dist[v.v] = dist[u] + v.w;
        dfs(v.v);
    }
}

void dfs2(int u, int par) {
    tin[u] = timer++;
    for(auto v : g[u]) {
        if(v.v == par) continue;
        dfs2(v.v, u);
    }
    tout[u] = timer++;
}

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }

void dfs3(int u, int par, int x) {
    if(is_ancestor(u, x)) mn = min(mn, max(dist[u], dist[x] - dist[u]));
    for(auto v : g[u]) {
        if(v.v == par) continue;
        dfs3(v.v, u, x);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int i = 0; i < m; i++) {
        g[a[i]].push_back({b[i], t[i]});
        g[b[i]].push_back({a[i], t[i]});
    }
    vector<int> W, W2;
    for(int i = 0; i < n; i++) {
        if(mark[i]) continue;
        component.clear();
        dfs(i);
        int mx = i;
        for(int j : component) if(dist[j] > dist[mx]) mx = j;
        for(int j : component) {
            dist[j] = 0;
            mark[j] = false;
        }
        component.clear();
        dfs(mx);
        int u, v;
        u = mx;
        mx = i;
        for(int j : component) if(dist[j] > dist[mx]) mx = j;
        v = mx;
        W.push_back(dist[mx]);
        dfs2(u, -1);
        mn = INT_MAX;
        dfs3(u, -1, v);
        W2.push_back(mn);
    }
    int res = 0;
    for(int i : W) res = max(res, i);
    sort(W2.rbegin(), W2.rend());
    if(W2.size() >= 2) res = max(res, W2[0] + W2[1] + l);
    if(W2.size() >= 3) res = max(res, W2[1] + W2[2] + 2 * l);
    return res;
}

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