Submission #1194061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194061		zaki98	Dreaming (IOI13_dreaming)	C++20	0 / 100	28 ms	10560 KiB

dreaming

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include "dreaming.h"
using namespace __gnu_pbds;
typedef long long ll;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) (c).begin(), (c).end()
#define pii pair<int,int>
#define pll pair<long long, long long>
#define sz(a) (int)a.size()
// permutation of the last layer
#define LOO(i,a,b) for (int i = a; i <= b; i++)
#define OOL(i,a,b) for (int i = b; i >= a; i--)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
using namespace std;

vector<vector<pii>> graph;
vector<bool> visited;
int best = 1e9;
vector<int> costs;
int dfs1(int index, int par) {
    int worsty = 0;
    for (pii xs: graph[index]) {
        int child = xs.F;
        int cost = xs.S;
        if (child==par) continue;
        worsty = max(worsty, dfs1(child, index)+cost);
    }
    costs[index] = worsty;
    visited[index] = true;
    return worsty;
}
int dfs2(int index, int par, int worst) {
    int worsty1 = 0;
    int index1 = -1;
    int worsty2 = 0;
    for (pii xs: graph[index]) {
        int child = xs.F;
        int cost = xs.S;
        if (child==par) continue;
        int final = cost+costs[child];
        if (final>=worsty1) {
            worsty2 = max(worsty2, worsty1);
            worsty1 = final;
            index1 = child;
        }
        else if (final>=worsty2) {
            worsty2 = final;
        }
    }
    if (max(worsty1, worst) < best) {
        best = max(worsty1, worst);
    }
    for (pii xs: graph[index]) {
        int child = xs.F;
        int cost = xs.S;
        if (child==par) continue;
        if (child==index1) {
            dfs2(child, index, max(worsty2+cost, worst + cost));
        }
        else {
            dfs2(child, index, max(worsty1+cost, worst + cost));
        }
    }
    visited[index] = true;
    return max(worsty1, worst);
}

int travelTime(int N,int M,int L, int A[],int B[],int T[]) {
    graph.resize(N);
    LOO(i, 0, M-1) {
        graph[A[i]].PB(MP(B[i], T[i]));
        graph[B[i]].PB(MP(A[i], T[i]));
    }
    visited = vector(N, false);
    costs.resize(N);
    LOO(i, 0, N-1) {
        if (visited[i]) continue;
        dfs1(i, i);
    }
    visited = vector(N, false);
    vector<int> unreal;
    LOO(i, 0, N-1) {
        if (visited[i]) continue;
        best = 1e9;
        dfs2(i, i, 0);
        unreal.PB(best);
    }
    sort(all(unreal));
    reverse(all(unreal));
    int best = unreal[0];
    LOO(i, 1, sz(unreal)-1) {
        best = max(best, unreal[0]+unreal[i]+L*i);
    }
    return best;
}

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