Submission #655402

#	Time	Username	Problem	Language	Result	Execution time	Memory
655402		ShirAriel	Forensic (NOI12_forensic)	C++17	25 / 25	3 ms	1492 KiB

forensic

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

vector<vector<ll>> branch;
vector<bool> bigchain;

ll getlen(ll v)
{
	ll ans = 1;

	for (ll i = 0; i < branch[v].size(); i++)
	{
		ll u = branch[v][i];
		if (!bigchain[u])
			ans = max(getlen(u) + 1, ans);
	}

	return ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll n;
	cin >> n;

	vector<ll> chain(n);
	for (ll i = 0; i < n; i++)
		cin >> chain[i];

	branch.resize(n);
	for (ll i = 0; i < n; i++)
		if (chain[i] != -1)
			branch[chain[i]].push_back(i);
	
	//find main chain
	bool circle = false;
	bigchain.resize(n, false);
	ll v = chain[0], cnt=0;
	bigchain[0] = true;
	while (v!=-1 && !bigchain[v])
	{
		bigchain[v] = true;
		v = chain[v];
		cnt++;
	}

	if (v != -1)
		circle = true;

	//find branches
	ll b = 0;
	v = chain[0];
	for (ll i = 0; i < cnt;i++)
	{
		b = max(b, getlen(v));
		v = chain[v];
	}

	//find other chains
	ll c = 0;
	for (ll i = 0; i < n; i++)
		if (chain[i] == -1 && !bigchain[i])
			c = max(c, getlen(i) + 1);

	if (circle&&c == 0)
		cout << cnt + 1;
	else
		cout << cnt + max(c, (circle ? 0 : b));

	return 0;
}

Compilation message (stderr)

forensic.cpp: In function 'll getlen(ll)':
forensic.cpp:16:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (ll i = 0; i < branch[v].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10