Submission #1318298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318298		Ekber_Ekber	Dreaming (IOI13_dreaming)	C++20	100 / 100	232 ms	18180 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
vector <pair<int, int>> g[MAX+2];
vector <int> dis(MAX+2), col(MAX+2, 0), p(MAX+2, 0);
vector <int> tp;
int w, ans;

void dfs(int u, int c=-1) {
    col[u] = 1;
    tp.pb(u);
    for (auto &i : g[u]) {
        if (i.ff == c) continue;
        dis[i.ff] = dis[u] + i.ss;
        p[i.ff] = u;
        dfs(i.ff, u);
        w += i.ss;
    }
}

int get(int u) {
    tp.clear();
    dis[u] = 0;
    dfs(u);
    int c = u;
    for (int &i : tp) {
        if (dis[c] < dis[i]) c = i;
    }
    tp.clear();
    dis[c] = 0;
    p[c] = -1;
    dfs(c);
    int c1 = c;
    for (int &i : tp) {
        if (dis[c1] < dis[i]) c1 = i;
    }
    vector <int> a;
    int c11 = c1;
    while (c1 != -1) {
        a.pb(c1);
        c1 = p[c1];
    }
    c1 = c11;
    int d = dis[c1], res = c;
    for (int &i : a) {
        int xr = max(dis[res], d - dis[res]);
        int xi = max(dis[i], d - dis[i]);
        if (xi < xr) res = i;
    }
    ans = max(ans, dis[c1]);
    return max(dis[res], d - dis[res]);
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < m; i++) {
        g[A[i] + 1].pb({B[i]+1, T[i]});
        g[B[i] + 1].pb({A[i]+1, T[i]});
    }
    vector <int> a;
    for (int i = 1; i <= n; i++) {
        if (col[i]) continue;
        a.pb(get(i));
    }
    sort(all(a),greater<int>());
    for (int &i : a) cerr << i << ' ';
    if (a.size() == 1) ans = max(ans, a[0]);
    else if (a.size() == 2) ans = max(ans, a[0] + a[1] + L);
    else ans = max({ans, a[0] + a[1] + L, a[1] + a[2] + 2 * 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