oj.uz

Submission #109961

# Submission time Handle Problem Language Result Execution time Memory
109961 2019-05-08T12:58:13 Z MetB Islands (IOI08_islands) C++14
80 / 100
 1194 ms 132096 KB 
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
 
typedef long long ll;
 
const ll MOD = 1e9 + 7, INF = 1e18;
 
using namespace std;

int n, m, p[1000001], cost[1000001];
bitset <1000000> is_cycle, u, c;
ll d[1000001][2], root[1000000];
ll pref[2000001];
deque < pair <ll, int> > q_max;

vector < pair <int, int> > g[1000001];
pair <int, int> g_un[1000001];

vector < pair <int, int> > cycle[1000001];

void bfs_traverse (ll x)
{
	queue <int> q;

	q.push (x);
	c[x] = 1;

	while (!q.empty ())
	{
		int x = q.front ();
		q.pop ();

		for (auto to : g[x])
			if (!c[to.first])
			{
				c[to.first] = 1;
				q.push (to.first);
			}
	}
}
 
bool bfs_cycle (ll x, ll color)
{
	while (!u[x])
	{
		u[x] = 1;
		p[g_un[x].first] = x;
		cost[g_un[x].first] = g_un[x].second;
		if (u[g_un[x].first] == 1) break;
		x = g_un[x].first;
	}

	int v = x;

	auto to = g_un[x];

	while (v != to.first)
	{
		cycle[color].emplace_back (v, cost[v]);
		is_cycle[v] = true;
		v = p[v];
	}
	cycle[color].emplace_back (to.first, to.second);
	is_cycle[to.first] = true;
	return true;
}

ll find_diameter (ll x)
{
	queue < pair <int, int> > q;

	int mx_i = x;

	q.push ({x, -1});
	c[x] = 1;

	while (!q.empty ())
	{
		int f = q.front ().first;
		int p = q.front ().second;
		q.pop ();

		if (d[mx_i][0] < d[f][0])
			mx_i = f;

		for (auto to : g[f])
			if ((!is_cycle[to.first] || to.first == x) && to.first != p)
			{
				d[to.first][0] = d[f][0] + to.second;
				c[to.first] = 1;
				q.push ({to.first, f});
			}
	}

	root[x] = d[mx_i][0];

	while (!q.empty ())
		q.pop ();

	q.push ({mx_i, -1});

	int dist = mx_i;

	while (!q.empty ())
	{
		int f = q.front ().first;
		int p = q.front ().second;
		q.pop ();

		if (d[dist][1] < d[f][1])
			dist = f;

		for (auto to : g[f])
			if ((!is_cycle[to.first] || to.first == x) && to.first != p)
			{
				d[to.first][1] = d[f][1] + to.second;
				c[to.first] = 1;
				q.push ({to.first, f});
			}
	}

	return d[dist][1];
}

ll process (vector < pair <int, int> > & cycle)
{
	ll diameter = 0;
	for (auto x : cycle)
		diameter = max (diameter, find_diameter (x.first));

	ll s = cycle.size ();

	for (ll i = 2 * cycle.size () - 1; i >= 0; i--)
		pref[i] = cycle[i % s].second + (i != 2 * cycle.size () - 1 ? pref[i+1] : 0);

	q_max.clear ();

	for (ll i = 0; i < s - 1; i++)
	{
		while (!q_max.empty () && q_max.back ().first <= pref[i] + root[cycle[i % s].first])
			q_max.pop_back ();

		q_max.emplace_back (pref[i] + root[cycle[i % s].first], i);
	}

	for (ll i = s - 1; i < 2 * cycle.size (); i++)
	{
		ll k = q_max.front ().first;
		diameter = max (diameter, k - pref[i] + root[cycle[i % s].first]);

		while (!q_max.empty () && q_max.back ().first <= pref[i] + root[cycle[i % s].first])
			q_max.pop_back ();

		q_max.emplace_back (pref[i] + root[cycle[i % s].first], i);

		while (!q_max.empty () && q_max.front ().second <= i - s + 1)
			q_max.pop_front ();
	}

	return diameter;
}

int main ()
{
	cin >> n;

	for (ll i = 0; i < n; i++)
	{
		ll x, l;

		scanf ("%lld%lld", &x, &l);

		g[i].emplace_back (x - 1, l);
		g[x - 1].emplace_back (i, l);

		g_un[i] = {x - 1, l};
	}

	ll color = 0;

	for (ll i = 0; i < n; i++)
		if (!u[i] && !c[i])
		{
			bfs_cycle (i, ++color);
			bfs_traverse (i);
		}


	ll ans = 0;

	for (ll i = 1; i <= color; i++)
		ans += process (cycle[i]);

	cout << ans;
}

Compilation message

islands.cpp: In function 'll process(std::vector<std::pair<int, int> >&)':
islands.cpp:145:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   pref[i] = cycle[i % s].second + (i != 2 * cycle.size () - 1 ? pref[i+1] : 0);
                                    ~~^~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:157:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (ll i = s - 1; i < 2 * cycle.size (); i++)
                     ~~^~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:182:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%lld%lld", &x, &l);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47360 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 44 ms 47352 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 47 ms 47352 KB Output is correct
6 Correct 44 ms 47360 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 52 ms 47372 KB Output is correct
9 Correct 45 ms 47284 KB Output is correct
10 Correct 44 ms 47480 KB Output is correct
11 Correct 57 ms 47452 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47436 KB Output is correct
2 Correct 48 ms 47480 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47480 KB Output is correct
2 Correct 49 ms 47716 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 48576 KB Output is correct
2 Correct 89 ms 50624 KB Output is correct
3 Correct 65 ms 48892 KB Output is correct
4 Correct 55 ms 48156 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 51800 KB Output is correct
2 Correct 101 ms 55488 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 63252 KB Output is correct
2 Correct 236 ms 63860 KB Output is correct
3 Correct 258 ms 72692 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 78184 KB Output is correct
2 Correct 418 ms 91180 KB Output is correct
3 Correct 526 ms 93188 KB Output is correct
4 Correct 551 ms 112064 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 118480 KB Output is correct
2 Runtime error 1194 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 125636 KB Output is correct
2 Correct 504 ms 118020 KB Output is correct
3 Runtime error 751 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -