제출 #1182266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182266		Nonoze	꿈 (IOI13_dreaming)	C++20	100 / 100	56 ms	24392 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define cmax(a, b) a=max(a, b)
#define cmin(a, b) a=min(a, b)
#define sz(x) (int)x.size()
#define fi first
#define se second
using namespace std;

int n, m, k, cur, mx=0;
vector<vector<pair<int, int>>> adj;
vector<int> dist;
vector<bool> vis;

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

void dfs2(int u, int p=-1, int act=0) {
	if (dist[u]<cur) cur=dist[u];
	cmax(mx, dist[u]);
	vis[u]=1;
	vector<pair<int, int>> children; children.pb({act, -1});
	for (auto [v, w]: adj[u]) if (v!=p) {
		children.pb({dist[v]+w, v});
	}
	sort(rall(children));
	for (auto [v, w]: adj[u]) if (v!=p) {
		int best=children[0].fi; if (children[0].se==v) best=children[1].fi;
		cmax(dist[v], best+w);
		dfs2(v, u, best+w);
	}
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n=N, m=M, k=L;
	adj.resize(n), dist.resize(n, -1);
	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 (dist[i]==-1) dfs(i);
	}
	vis.resize(n);
	vector<int> vec;
	for (int i=0; i<n; i++) {
		if (!vis[i]) {
			cur=dist[i];
			dfs2(i);
			vec.pb(cur);
		}
	}
	sort(rall(vec));
	for (int i=1; i<sz(vec); i++) {
		int du=vec[i-1], dv=vec[i];
		cmax(mx, du+k+dv);
		cmax(vec[i-1], du+k), cmax(vec[i], dv+k);
		if (vec[i-1]<vec[i]) swap(vec[i], vec[i-1]);
	}
	return 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