Submission #655398

#	Time	Username	Problem	Language	Result	Execution time	Memory
655398		ShirAriel	연결리스트 수사하기 (NOI12_forensic)	C++17	20 / 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> visited;

ll getlen(ll v)
{
	ll ans = 0;
	visited[v] = true;

	for (ll i = 0; i < branch[v].size(); i++)
	{
		ll u = branch[v][i];
		if (!visited[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);
		

	ll b = 0, c = 0;
	bool circle = false;
	visited.resize(n, false);

	ll v = chain[0], cnt=1;
	visited[0] = true;
	while (v!=-1 && !visited[v])
	{
		visited[v] = true;
		b = max(b, getlen(v));
		v = chain[v];
		cnt++;
	}

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

	for (ll i = 0; i < n; i++)
		if (chain[i] == -1 && !visited[i])
			c = max(c, getlen(i) + 1);

	cout << cnt + max(c, (circle ? 0 : b));

	return 0;
}

Compilation message (stderr)

forensic.cpp: In function 'll getlen(ll)':
forensic.cpp:17: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]
   17 |  for (ll i = 0; i < branch[v].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~~

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