oj.uz

Submission #881984

# Submission time Handle Problem Language Result Execution time Memory
881984 2023-12-02T11:26:48 Z serifefedartar Dreaming (IOI13_dreaming) C++17
0 / 100
 46 ms 29268 KB 
#include <bits/stdc++.h>
#include"dreaming.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;

vector<vector<pair<int,int>>> graph;
int vis[MAXN], up[MAXN], mx[MAXN];
pair<int,int> st[MAXN];
int dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		int Q = u.s + dfs(u.f, node);
		if (Q > st[node].f)
			st[node] = {Q, st[node].f};
		else if (Q > st[node].s)
			st[node] = {st[node].f, Q};
	}
	return st[node].f;
}

void dfs2(int node, int parent, int par_len) {
	vis[node] = true;
	if (node != parent) {
		int th = st[node].f + par_len;
		up[node] = up[parent] + par_len;
		if (th == st[parent].f)
			up[node] = max(up[node], st[parent].s + par_len);
		else
			up[node] = max(up[node], st[parent].f + par_len);
	}
	mx[node] = max(up[node], st[node].f);

	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs2(u.f, node, u.s);
	}
}

int mx_node = 0, mx_dist = -1;
void dfs3(int node, int parent, int dist) {
	if (dist > mx_dist) {
		mx_dist = dist;
		mx_node = node;
	}

	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs3(u.f, node, dist + u.s);
	}
}

int diameter(int node) {
	mx_dist = -1, mx_node = 0;
	dfs3(node, node, 0);
	int q = mx_node;
	dfs3(q, q, 0);
	return mx_dist;
}

int nd = 0;
void dfs4(int node, int parent) {
	vis[node] = true;
	if (mx[node] > nd)
		nd = mx[node];
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs4(u.f, node);
	}
}

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

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

	for (int i = 1; i <= N; i++)
		vis[i] = false;
	priority_queue<pair<int,int>> pq;
	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			int dia = diameter(i);
			nd = 0;
			dfs4(i, i);
			pq.push({nd, dia});
		}
	}

	while (pq.size() >= 2) {
		pair<int,int> A = pq.top();
		pq.pop();
		pair<int,int> B = pq.top();
		pq.pop();
		
		int new_dia = max(A.s, max(B.s, A.f + B.f + L));
		int new_mx = min(max(A.f, B.f + L), max(A.f + L, B.f));
		pq.push({new_mx, new_dia});
	}

	cout << pq.top().s << "\n";
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:120:1: warning: no return statement in function returning non-void [-Wreturn-type]
  120 | }
      | ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 29268 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 29268 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 15848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 4700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 29268 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -