Submission #1241814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241814		Minbaev	Dreaming (IOI13_dreaming)	C++20	100 / 100	72 ms	27356 KiB

dreaming

 #include "dreaming.h"
//#include "grader.c"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const long long inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int md = 998244353;

vector<ar<int,2>>g[100005], cycle;
vector<int>mx(100005), vis(100005);

void dfs(int x, int pr){
    vis[x] = 1;
    for(auto [to, cost] : g[x]){
        if(to == pr)continue;
        dfs(to, x);
        umax(mx[x], mx[to] + cost);
    }
}

void fmx(int x, int pr, int a){
    umax(mx[x], a);
    cycle.pb({mx[x], x});

    vis[x] = 1;
    vector<ar<int,2>>vs;
    for(auto [to, cost] : g[x]){
        if(to == pr)continue;
        vs.pb({mx[to] + cost, to});
    }

    sort(all(vs));
    reverse(all(vs));
    // if(x == 1){
        // for(auto to:vs)cout << to[0] << " " << to[1] << "\n";
        // cout << "\n";
    // }

    for(auto [to, cost] : g[x]){
        if(to == pr)continue;
        if(to == vs[0][1]){
            if(vs.size() > 1)
                fmx(to, x, max(a, vs[1][0]) + cost);
            else
                fmx(to, x, a + cost);
        }
        else{
            fmx(to, x, max(a, vs[0][0]) + cost);
        }
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    // cout << 1 << "\n";
    // exit(0);
    for(int i = 0;i<M;i++){
        g[A[i]].pb({B[i], T[i]});
        g[B[i]].pb({A[i], T[i]});
    }

    for(int i = 0;i<N;i++){
        if(vis[i])continue;
        dfs(i, -1);
    }
    // cout << 0 << "\n";
    // exit(0);
    for(int i = 0;i<N;i++){
        vis[i] = 0;
    }

    vector<ar<int,2>>vs;
    // cout << mx[5] << "\n";

    for(int i = 0;i<N;i++){
        if(vis[i])continue;
        cycle.clear();
        fmx(i, -1, 0);
        sort(all(cycle));
        vs.pb({cycle[0][0], cycle[0][1]});
    }

    sort(all(vs));
    reverse(all(vs));

    int u = N - M - 1;
    int i = 1;
    while(u > 0){
        u -= 1;
        g[vs[0][1]].pb({vs[i][1], L});
        g[vs[i][1]].pb({vs[0][1], L});
        i += 1;
    }

    for(int i = 0;i<N;i++){
        mx[i] = 0;
        vis[i] = 0;
    }

    dfs(0, -1);
    for(int i = 0;i<N;i++){
        vis[i] = 0;
    }

    fmx(0, -1, 0);

    return *max_element(all(mx));

}

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