Submission #1178032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178032		lrnnz	Dreaming (IOI13_dreaming)	C++17	100 / 100	55 ms	16792 KiB

dreaming

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include "dreaming.h"
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
 
/********* DEBUG *********/
 
template <typename T>
void outvec(const vector<T>& Z){
    for (const T& x : Z)
    cout << x << ' ';
    cout << "\n";
}

void printVariable(const any& var) {
    if (!var.has_value()) {
        cout << "null";
        return;
    }

    if (var.type() == typeid(int)) {
        cout << any_cast<int>(var);
    } else if (var.type() == typeid(double)) {
        cout << any_cast<double>(var);
    } else if (var.type() == typeid(float)) {
        cout << any_cast<float>(var);
    } else if (var.type() == typeid(char)) {
        cout << any_cast<char>(var);
    } else if (var.type() == typeid(bool)) {
        cout << (any_cast<bool>(var) ? "true" : "false");
    } else if (var.type() == typeid(string)) {
        cout << any_cast<string>(var);
    } else if (var.type() == typeid(const char*)) {
        cout << any_cast<const char*>(var);
    } else if (var.type() == typeid(long long)) {
        cout << any_cast<long long>(var);
    } else {
        cout << "[unknown type]";
    }
}

template<typename... Args>
void outval(Args... args) {
    vector<any> variables = {args...};
    
    for (size_t i = 0; i < variables.size(); ++i) {
        printVariable(variables[i]);
        if (i != variables.size() - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

/********* DEBUG *********/

const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1000000000;
const ll needMOD = 987654321; 
const ll mxN = 100005;
const ll inf = 1e18;

/*                                    idea
    answer is equal to max(top1 + top2 + L, top2 + top3 + L * 2, topdiameter)
    just implement finding the diameter and radius of each connected component
*/
void solve() { 

}   

ll tpdia, ccrad[3], currdia, farnd, lorad, currad;
bool fndrad;

void updcc(ll val){
    for (int i = 0; i < 3; i++){
        if (val > ccrad[i]){
            swap(val,ccrad[i]);
        }
    }
}

// return if we reach end leaf
bool dfs(ll nd, vector<vector<pair<ll,ll>>> &adj, ll par = -1, ll dep = 0){
    if (dep > currdia){
        currdia = dep;
        farnd = nd;
    }

    bool reach = dep==currdia;
    
    //if (fndrad)
    //cout << "cl nd, dep: " << nd << ' ' << dep << "\n";

    for (auto &[newnd, cst] : adj[nd]){
        if (newnd==par)
        continue;

        reach = reach | dfs(newnd, adj, nd, dep+cst);
    }

    if (fndrad){
        if (reach){
            if (currad==0)
            currad=max(dep,currdia-dep);
            currad=min(currad, max(dep, currdia-dep));
        }
        adj[nd].clear();
    }

    return reach;
}

void take(ll nd, vector<vector<pair<ll,ll>>> &adj, ll cst = 0, ll par = -1){
    farnd=currdia=fndrad=0;
    dfs(nd, adj);
    currdia=0;
    //cout << farnd << "\n";
    dfs(farnd, adj);

    tpdia=max(tpdia, currdia);
    // now we have diameter of the current CC = currdia
    // find radius now

    lorad=currad=0;
    fndrad=true;
    dfs(farnd, adj);
    
    lorad=max(lorad,currad);
    // now we have radius of graph, update the ccrads and done
    updcc(currad);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    tpdia=0;
    memset(ccrad, 0, 3);

    // nd, cst
    vector<vector<pair<ll,ll>>> adj(N);
    for (int i = 0; i < M; i++){
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }

    for (int i = 0; i < N; i++){
        if (sz(adj[i]) == 1){
            take(i, adj);
        }
    }
    
    int ans = tpdia;
    if (M < N-1)
        ans = max(ans, (int)ccrad[0] + (int)ccrad[1] + L);

    if (M < N-2)
        ans = max(ans, (int)ccrad[1] + (int)ccrad[2] + L * 2);

    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