Submission #881011

#	Time	Username	Problem	Language	Result	Execution time	Memory
881011		sysia	Dreaming (IOI13_dreaming)	C++17	0 / 100	38 ms	16940 KiB

dreaming

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "dreaming.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << "'" << x << "'";}
void __print(const char *x) {cout << '"' << x << '"';}
void __print(const string &x) {cout << '"' << x << '"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ", "; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo = 1e9+7, K = 30;
const int mod = 998244353;

int travelTime(int n, int m, int L, int A[], int B[], int TT[]) {
    vector<vector<T>>g(n);
    for (int i = 0; i<m; i++){
        // debug(A[i], B[i], TT[i]);
        g[A[i]].emplace_back(B[i], TT[i]);
        g[B[i]].emplace_back(A[i], TT[i]);
    }
    vector<bool>vis(n);
    vector<int>depth(n), par(n);
    T curr = {-oo, -oo};
    function<void(int, int)>dfs = [&](int v, int pa){
        vis[v] = 1;
        par[v] = pa;
        curr = max(curr, {depth[v], v});
        for (auto [x, c]: g[v]){
            if (x == pa) continue;
            depth[x] = depth[v]+c;
            dfs(x, v);
        }
    };
    int mx1 = 0, mx2 = 0;
    for (int i = 0; i<n; i++){
        if (!vis[i]){
            curr = {-oo, -oo};
            dfs(i, i);
            int R = curr.second;
            dfs(curr.second, curr.second);
            int L = curr.second;
            // debug(L, R);
            depth[L] = 0;
            dfs(L, L);
            int w = depth[R];
            int v = R, c = oo;
            while (1){
                c = min(c, max(depth[v], w-depth[v]));
                v = par[v];
                if (v == L) break;
            }
            // debug(w, c);
            if (c >= mx1){
                mx2 = mx1;
                mx1 = c;
            } else if (c >= mx2){
                mx2 = c;
            }
        }
    }
    // debug(mx1, mx2, L);
    return mx1+mx2+(m == n-1 ? 0 : L);
}

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