Submission #561127

#	Time	Username	Problem	Language	Result	Execution time	Memory
561127		Zanite	꿈 (IOI13_dreaming)	C++17	100 / 100	143 ms	23880 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int INF = 2e9;
const int maxN = 1e5 + 5;

void chmax(int &a, int b) {a = max(a, b);}
void chmin(int &a, int b) {a = min(a, b);}

struct Node {
    int child, lg;
    Node(int _child, int _lg) :
        child(_child),
        lg(_lg)
    {}

    bool operator < (const Node &other) const {
        return lg > other.lg;
    }
};

int N, M, L, ans;
vector<pii> adj[maxN];
vector<Node> children[maxN];
int idx[maxN], longest[maxN], newLongest[maxN];

vector<int> curComponent, components;
void dfs(int cur, int par, int id) {
    idx[cur] = id;
	curComponent.push_back(cur);

    for (auto a : adj[cur]) {
        int nxt, w;
        tie(nxt, w) = a;
        if (nxt == par) continue;

        dfs(nxt, cur, id);
        chmax(longest[cur], longest[nxt] + w);
        children[cur].push_back(Node(nxt, longest[nxt] + w));
    }
}

void reroot(int cur, int par, int downwardsEdge) {
    if (par != -1) {
        // push "parent" as cur's child
        if (children[par][0].child == cur) {
            if (children[par].size() > 1) {
                children[cur].push_back(Node(par, children[par][1].lg + downwardsEdge));
            } else {
                children[cur].push_back(Node(par, downwardsEdge));
            }
            
        } else {
            children[cur].push_back(Node(par, children[par][0].lg + downwardsEdge));
        }
    }

	sort(children[cur].begin(), children[cur].end());

	// update newLongest
	for (auto c : children[cur]) {
		chmax(newLongest[cur], c.lg);
	}

	// go to children
	for (auto a : adj[cur]) {
		int nxt, w;
		tie(nxt, w) = a;
		if (nxt == par) continue;

		reroot(nxt, cur, w);
	}
}

void calculateTree(int root, int id) {
    // gather data about longest and children's longest for each node
	curComponent.clear();
    dfs(root, -1, id);

    // do reroot
    reroot(root, -1, -1);

	// find out the minimum newLongest of the component
	int curMin = INF;
	for (auto i : curComponent) {
		chmax(ans, newLongest[i]);
		chmin(curMin, newLongest[i]);
	}
	components.push_back(curMin);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }

    for (int i = 0, cur = 1; i < N; i++) {
        if (idx[i] == 0) {
            calculateTree(i, cur);
            cur++;
        }
    }

	sort(components.begin(), components.end());
	int s = components.size();

	if (s > 1) {
		chmax(ans, components[s-1] + components[s-2] + L);
	}
	if (s > 2) {
		chmax(ans, components[s-2] + components[s-3] + (L << 1));
	}
	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