제출 #411305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411305		islander7	꿈 (IOI13_dreaming)	C++17	40 / 100	1085 ms	38856 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair <ll, int>
using namespace std;
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	map <int, vector <pii>> adj;
	map <int, vector <int>> cc;
	map <pii, int> edges;
	map <int, int> ccnum;
	int maxgrp;
	ll maxlen = 0;
	ll m1 = -1, m2 = -1, m3 = -1;
	for (int i = 0; i < M; i++)
	{
		adj[A[i]].push_back(make_pair(B[i], T[i]));
		adj[B[i]].push_back(make_pair(A[i], T[i]));
		edges[make_pair(A[i], B[i])] = T[i];
		edges[make_pair(B[i], A[i])] = T[i];
	}
	int cur = 0;
	for (int i = 0; i < N; i++)
	{
		ccnum[i] = -1;
	}
	for (int i = 0; i < N; i++)
	{
		if (ccnum[i] == -1)
		{
			queue <int> curs;
			curs.push(i);
			ccnum[i] = cur;
			while (!curs.empty())
			{
				int a = curs.front();
				curs.pop();
				for (auto x : adj[a])
				{
					if (ccnum[x.first] == -1)
					{
						ccnum[x.first] = cur;
						curs.push(x.first);
					}
				}
			}
			cur++;
		}
	}
	for (int i = 0; i < N; i++)
	{
		cc[ccnum[i]].push_back(i);
	}
	maxgrp = cur - 1;
	for (int i = 0; i <= maxgrp; i++)
	{
		if (cc[i].size() == 1)
		{
			if (m3 < 0)
			{
				m3 = 0;
				if (m3 > m2)
				{
					swap(m3, m2);
					if (m2 > m1)
					{
						swap(m2, m1);
					}
				}
			}
			continue;
		}
		map <int, ll> mins;
		for (int a : cc[i])
		{
			mins[a] = -1;
		}
		mins[cc[i][0]] = 0;
		queue <int> curs;
		curs.push(cc[i][0]);
		while (!curs.empty())
		{
			int a = curs.front();
			curs.pop();
			for (auto b : adj[a])
			{
				if (mins[b.first] == -1)
				{
					curs.push(b.first);
					mins[b.first] = mins[a] + edges[make_pair(a, b.first)];
				}
			}
		}
		int maxl = 0;
		int far = 0;
		for (int a : cc[i])
		{
			if (mins[a] > maxl)
			{
				maxl = mins[a];
				far = a;
			}
		}
		map <int, int> parent;
		for (int a : cc[i])
		{
			mins[a] = -1;
		}
		mins[far] = 0;
		curs.push(far);
		while (!curs.empty())
		{
			int a = curs.front();
			curs.pop();
			for (auto b : adj[a])
			{
				if (mins[b.first] == -1)
				{
					curs.push(b.first);
					mins[b.first] = mins[a] + edges[make_pair(a, b.first)];
					parent[b.first] = a;
				}
			}
		}
		maxl = 0;
		int far2 = 0;
		for (int a : cc[i])
		{
			if (mins[a] > maxl)
			{
				maxl = mins[a];
				far2 = a;
			}
		}
		int start = far;
		int end = far2;
		ll length = mins[far2];
		ll tot = 0;
		if (length > maxlen)
		{
			maxlen = length;
		}
		int curpos = far2;
		int minmax = 0;
		while (tot * 2 < length)
		{
			tot += edges[make_pair(curpos, parent[curpos])];
			if (tot * 2 == length)
			{
				minmax = tot;
			}
			if (tot * 2 > length)
			{
				if (tot * 2 - edges[make_pair(curpos, parent[curpos])] >= length)
				{
					minmax = length - tot + edges[make_pair(curpos, parent[curpos])];
				}
				else
				{
					minmax = tot;
				}
			}
			curpos = parent[curpos];
		}
		if (m3 < minmax)
		{
			m3 = minmax;
			if (m3 > m2)
			{
				swap(m3, m2);
				if (m2 > m1)
				{
					swap(m2, m1);
				}
			}
		}
	}
	if (m2 == -1)
	{
		return max(maxlen, m1);
	}
	else if (m3 == -1)
	{
		return max(maxlen, m1 + L + m2);
	}
	else
	{
		return max(maxlen, max(m1 + L + m2, m2 + m3 + 2 * L));
	}
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:139:7: warning: unused variable 'start' [-Wunused-variable]
  139 |   int start = far;
      |       ^~~~~
dreaming.cpp:140:7: warning: unused variable 'end' [-Wunused-variable]
  140 |   int end = far2;
      |       ^~~

• Subtask 1: 0 / 14
• Subtask 2: 10 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23