Submission #1147742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147742		KickingKun	Dreaming (IOI13_dreaming)	C++20	18 / 100	218 ms	131072 KiB

dreaming

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

const int LIM = 1e5 + 5;
vector <pair <int, int>> adj[LIM];
int dist[LIM];

void add_edge(int u, int v, int w) {
	adj[u].emplace_back(v, w);
	adj[v].emplace_back(u, w);
//	cerr << u << ' ' << v << ' ' << w << '\n';
}

void dfs(int u, int p = -1) {
	for (auto [v, w]: adj[u]) if (v != p) {
		dist[v] = dist[u] + w;
		dfs(v, u);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int root = -1, v = -1, ma = 0;
    vector <bool> alone(N, true);
    for (int i = 0; i < M; i++) {
    	if (T[i] > ma) root = A[i], v = B[i], ma = T[i];
    	alone[A[i]] = alone[B[i]] = false;
    }
    
	for (int i = 0; i < M; i++) {
		add_edge(A[i], B[i], T[i]);
	}

    for (int i = 0; i < N; i++) {
		if (alone[i]) add_edge(root, i, L);
	}
	
	for (int i = 0; i < M; i++) {
		if (A[i] != root && B[i] != root)
			add_edge(root, A[i], L);
	}
	
	dfs(root); int leaf = -1, maDis = 0;
	for (int i = 0; i < N; i++)
		if (maDis < dist[i]) {
			maDis = dist[i];
			leaf = i;
		}
	
	dist[leaf] = 0; dfs(leaf);
	return *max_element(dist, dist + N);
}

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