oj.uz

Submission #109908

# Submission time Handle Problem Language Result Execution time Memory
109908 2019-05-08T11:26:06 Z MetB Islands (IOI08_islands) C++14
21 / 100
 495 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, is_cycle[1000000], u[1000000], d[1000000][2], cost[1000000], p[1000000];
int c[1000000];

vector < pair <int, int> > g[1000000], g_t[1000000];

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

void dfs_traverse (int x)
{
	c[x] = 1;

	for (auto to : g[x])
		if (!c[to.first])
			dfs_traverse (to.first);
}
 
bool dfs_cycle (int x, int par, int color)
{
	u[x] = 1;
	
	for (auto to : g_t[x])
	{
		if (u[to.first] == 1)
		{
			int v = 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;
		}
		else if (!u[to.first])
		{
			p[to.first] = x;
			cost[to.first] = to.second;
			if (dfs_cycle (to.first, x, color)) return true;
		}
	}

	u[x] = 2;

	return false;
}

int find_diameter (int x, int p)
{
	int sum = 0, mx = 0, smx = 0;

	for (auto to : g[x])
		if (to.first != p && !is_cycle[to.first])
		{
			sum = max (sum, find_diameter (to.first, x));

			if (mx <= d[to.first][0] + to.second)
			{
				smx = mx;
				mx = d[to.first][0] + to.second;
			}
			else smx = max (smx, d[to.first][0] + to.second);
		}

	d[x][0] = mx;
	d[x][1] = smx;
	return max (sum, mx + smx);
}

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

	int s = cycle.size ();
	for (int i = 0; i < s; i++)
		cycle.push_back (cycle[i]);

	vector <int> pref (cycle.size ());

	for (int i = cycle.size () - 1; i >= 0; i--)
		pref[i] = cycle[i].second + (i != cycle.size () - 1 ? pref[i+1] : 0);

	deque < pair <int, int> > q_max;

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

		q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);
	}

	for (int i = s - 1; i < cycle.size (); i++)
	{
		int k = q_max.front ().first;
		diameter = max (diameter, k - pref[i] + d[cycle[i].first][0]);

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

		q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);

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

	reverse (cycle.begin(), cycle.end());

	pref[cycle.size () - 1] = cycle[0].second;
	for (int i = cycle.size () - 2; i >= 0; i--)
		pref[i] = pref[i + 1] + cycle[i + 1].second;

	q_max.clear ();

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

		q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);
	}

	for (int i = s - 1; i < cycle.size (); i++)
	{
		diameter = max (diameter, q_max.front ().first - pref[i] + d[cycle[i].first][0]);

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

		q_max.emplace_back (pref[i] + d[cycle[i].first][0], i);

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

	return diameter;
}

int main ()
{
	cin >> n;

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

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

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

	int color = 0;

	for (int i = 0; i < n; i++)
		if (!u[i] && !c[i])
		{
			dfs_cycle (i, -1, ++color);
			dfs_traverse (i);
		}

	int ans = 0;

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

	cout << ans;
}

Compilation message

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

Subtask #1
21.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 70776 KB Output is correct
2 Correct 72 ms 70776 KB Output is correct
3 Incorrect 77 ms 70904 KB Output isn't correct
4 Correct 72 ms 70776 KB Output is correct
5 Correct 68 ms 70776 KB Output is correct
6 Correct 70 ms 70860 KB Output is correct
7 Correct 70 ms 70904 KB Output is correct
8 Incorrect 76 ms 70904 KB Output isn't correct
9 Incorrect 68 ms 70776 KB Output isn't correct
10 Correct 74 ms 70916 KB Output is correct
11 Incorrect 67 ms 70904 KB Output isn't correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 410 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 495 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -