oj.uz

답안 #655398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655398 2022-11-04T08:39:06 Z ShirAriel 연결리스트 수사하기 (NOI12_forensic) C++17
20 / 25
 3 ms 1492 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 0 ms 316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1240 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 1492 KB Output is correct
5 Correct 2 ms 852 KB Output is correct