Submission #399041

#	Time	Username	Problem	Language	Result	Execution time	Memory
399041		prvocislo	Dreaming (IOI13_dreaming)	C++17	47 / 100	99 ms	24768 KiB

dreaming

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include"dreaming.h"
typedef long long ll;
using namespace std;

const int maxn = 1e5 + 79, inf = 1e9 + 79;
vector<int> vis(maxn, 0), dp(maxn, 0);
vector<vector<pair<int, int> > > g(maxn);
void dfs1(int u, int p)
{
	vis[u] = 1;
	for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; }
	for (pair<int, int> i : g[u])
	{
		dfs1(i.first, u);
		dp[u] = max(dp[u], dp[i.first] + i.second);
	}
}
void dfs2(int u, int dist, int &mini, int &dia)
{
	mini = min(mini, max(dist, dp[u]));
	vector<int> pf(g[u].size() + 1, 0), sf(g[u].size() + 1, 0);
	pair<int, int> p(0, 0);
	for (int i = 0; i < g[u].size(); i++)
	{
		int di = dp[g[u][i].first] + g[u][i].second; pf[i + 1] = max(pf[i], di);
		if (di > p.first) swap(p.first, p.second), p.first = di;
		else if (di > p.second) p.second = di;
	} 
	dia = max({ dia, p.first + p.second, dp[u] + dist });
	for (int i = g[u].size() - 1; i >= 0; i--)
		sf[i] = max(sf[i + 1], dp[g[u][i].first] + g[u][i].second);
	for (int i = 0; i < g[u].size(); i++)
		dfs2(g[u][i].first, max({ dist, pf[i], sf[i + 1] }) + g[u][i].second, mini, dia);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
	for (int i = 0; i < m; i++)
		g[a[i]].push_back({ b[i], t[i] }), g[b[i]].push_back({ a[i], t[i] });
	vector<int> v; int ans = 0;
	for (int i = 0; i < n; i++)
		if (!vis[i])
		{
			v.push_back(inf);
			dfs1(i, -1), dfs2(i, 0, v.back(), ans);
		}
	return max(v[0] + l + v[1], ans);
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i = 0; i < g[u].size(); i++) if (g[u][i].first == p) { g[u].erase(g[u].begin() + i); break; }
      |                  ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int&, int&)':
dreaming.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i = 0; i < g[u].size(); i++)
      |                  ~~^~~~~~~~~~~~~
dreaming.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < g[u].size(); i++)
      |                  ~~^~~~~~~~~~~~~

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