Submission #1263289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263289		aren_dance	Dreaming (IOI13_dreaming)	C++20	24 / 100	44 ms	22340 KiB

dreaming

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int N = 3e5+1;
vector<pair<int, int>> g[N];
int dp[N];
int depth[N];
int mx[N];
bool vis[N];
vector<int> gag[2];
int o;
vector<pair<int,int>> hert;
void dfs2(int v,int p) {
    mx[v] = depth[v];
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        depth[i.first] = depth[v] + i.second;
        dfs2(i.first,v);
        mx[v] = max(mx[i.first], mx[v]);
    }
    dp[v] = mx[v] - depth[v];
    vector<int> mas;
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        mas.push_back(mx[i.first]);
    }
    if (mas.empty() || mas.size()==1) {
        return;
    }
    sort(mas.rbegin(), mas.rend());
    dp[v] = max(dp[v],mas[0] + mas[1] - 2*depth[v]);
}
int get() {
    for (int i = 0;i < o;++i) {
        dp[i] = 0;
        mx[i] = 0;
        depth[i] = 0;
    }
    dfs2(0,-1);
    int answ = 0;
    for (int i = 0;i < o;++i) {
        answ = max(answ, dp[i]);
    }
    return answ;
}
void dfs(int v,int comp) {
    vis[v] = 1;
    gag[comp].push_back(v);
    for (auto i : g[v]) {
        if (!vis[i.first]) {
            dfs(i.first, comp);
        }
    }
}
void dfs3(int v,int p,int dep) {
    hert.push_back({v, dep });
    for (auto i:g[v]) {
        if (i.first == p) {
            continue;
        }
        dfs3(i.first, v, dep + i.second);
    }
}
int travelTime(int n, int m, int l,
    int a[], int b[], int t[]) {
    o = n;
    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] });
    }
    int cnt = 0;
    for (int i = 0;i < n;++i) {
        if (!vis[i]) {
            dfs(i, cnt);
            ++cnt;
        }
    }
    if (n <= 100) {
        int answ = 1e9;
        for (auto i : gag[0]) {
            for (auto j : gag[1]) {
                g[i].push_back({ j,l });
                g[j].push_back({ i,l });
                int p = get();
                answ = min(answ, p);
                g[i].pop_back();
                g[j].pop_back();
            }
        }
        return answ;
    }
    int p1 = 1;
    for (auto i : gag[0]) {
        if (g[i].size() == 1) {
            p1 = i;
            break;
        }
    }
    dfs3(p1, -1, 0);
    int mn = 0;
    int answ = 1e9;
    for (auto i : hert) {
        int h = max(i.second, hert.back().second - i.second);
        if (answ > h) {
            answ = h;
            mn = i.first;
        }
    }
    hert.clear();
    for (auto i : gag[1]) {
        if (g[i].size() == 1) {
            p1 = i;
            break;
        }
    }
    dfs3(p1, -1, 0);
    int mn2 = 0;
    answ = 1e9;
    for (auto i : hert) {
        int h = max(i.second, hert.back().second- i.second);
        if (answ > h) {
            answ = h;
            mn2 = i.first;
        }
    }
    g[mn].push_back({ mn2,l });
    g[mn2].push_back({ mn,l });
    return get();
}

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