oj.uz

Submission #28839

# Submission time Handle Problem Language Result Execution time Memory
28839 2017-07-17T09:50:23 Z nibnalin Dreaming (IOI13_dreaming) C++14
0 / 100
 86 ms 15348 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include "dreaming.h"
using namespace std;

const int maxn = int(1e5)+5, inf = int(1e9)+5;

int n, m, l, D[2][maxn], vis[maxn];
vector<int> cur_comp;
vector<pair<int, int>> guys, graph[maxn];

int dfs(int node, int par, int d, int type)
{
	D[type][node] = d;
	if(type) cur_comp.push_back(node);
	int cur = node;
	for(auto it: graph[node])
	{
		if(it.first != par)
		{
			int tmp = dfs(it.first, node, d+it.second, type);
			if(D[type][cur] < D[type][tmp]) cur = tmp;
		}
	}
	return cur;
}


int travelTime(int _N, int _M, int _L, int _A[], int _B[], int _T[]) {
	n = _N, m = _M, l = _L;
	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]});
	}

	int res = -1;
	set<pair<int, int>, greater<pair<int, int>>> S;
	for(int i = 0;i < n;i++)
	{
		if(!vis[i])
		{
			cur_comp.clear();
			int f1 = dfs(i, -1, 0, 0);
			int f2 = dfs(f1, -1, 0, 0);
			dfs(f2, -1, 0, 1);
			pair<int, int> mini = {inf, inf};
			for(auto it: cur_comp)
			{
				mini = min(mini, {max(D[0][it], D[1][it]), it});
				vis[it] = 1;
			}
			res = max(res, D[0][f2]);
			//cout << mini.first << " " << mini.second << "\n";
			guys.push_back(mini);
			S.insert(mini);
		}
	}

	int res2 = inf;
	for(auto it: guys)
	{
		if(int(S.size()) < 2) continue;
		S.erase(it), S.insert({it.first-2, it.second});

		int tmp = l*2+((S.begin()->first)+(next(S.begin())->first));
		res2 = min(res2, tmp);

		S.insert(it), S.erase({it.first-2, it.second});
	}

	return max(res, res2);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15348 KB Output is correct
2 Correct 70 ms 15324 KB Output is correct
3 Correct 42 ms 11004 KB Output is correct
4 Correct 11 ms 4608 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 18 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15348 KB Output is correct
2 Correct 70 ms 15324 KB Output is correct
3 Correct 42 ms 11004 KB Output is correct
4 Correct 11 ms 4608 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 18 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15348 KB Output is correct
2 Correct 70 ms 15324 KB Output is correct
3 Correct 42 ms 11004 KB Output is correct
4 Correct 11 ms 4608 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 18 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 9556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15348 KB Output is correct
2 Correct 70 ms 15324 KB Output is correct
3 Correct 42 ms 11004 KB Output is correct
4 Correct 11 ms 4608 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 18 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15348 KB Output is correct
2 Correct 70 ms 15324 KB Output is correct
3 Correct 42 ms 11004 KB Output is correct
4 Correct 11 ms 4608 KB Output is correct
5 Correct 10 ms 3712 KB Output is correct
6 Correct 18 ms 5504 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -