oj.uz

Submission #964379

# Submission time Handle Problem Language Result Execution time Memory
964379 2024-04-16T18:07:54 Z raspy Dreaming (IOI13_dreaming) C++14
0 / 100
 41 ms 14928 KB 
#include "dreaming.h"

#include <iostream>
#include <vector>
#include <queue>

#define inf 10000000

using namespace std;

vector<pair<int, int>> graf[200005];
int ob[200005];
int mx[200005];
int ixm[200005];
int zc = 0;

int dfs(int u)
{
	if (ob[u])
		return 0;
	ob[u] = 1;
	int ix = 0;
	for (auto [v, w] : graf[u])
	{
		if (!ob[v])
		{
			int tr = dfs(v)+w;
			if (tr > mx[u])
			{
				zc = mx[u];
				mx[u] = tr;
				ixm[u] = ix;
			}
			else
				zc = mx[u];
		}
		ix++;
	}
	return mx[u];
}

int getBest(int u, int trd)
{
	if (ob[u] == 2)
		return inf;
	// cout << u << " " << trd << " " << mx[u] << "\n";
	if (trd < mx[u])
		return min(getBest(graf[u][ixm[u]].first, trd+graf[u][ixm[u]].second), mx[u]);
	return trd;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
	// cout << n << " " << m << "\n";
	for (int i = 0; i < m; i++)
	{
		graf[a[i]].push_back({b[i], t[i]});
		graf[b[i]].push_back({a[i], t[i]});
	}
	priority_queue<int> pq;
	for (int i = 0; i < n; i++)
		if (!ob[i])
		{
			zc = 0;
			// cout << i << " " << "test\n";
			dfs(i);
			int tr = getBest(i, zc);
			// cout << tr << "\n";
			pq.push(tr);
		}
	int rez = 0;
	if (pq.size() >= 2)
	{
		rez += pq.top() + l;
		pq.pop();
		rez += pq.top();
	}
	return rez;
}

Compilation message

dreaming.cpp: In function 'int dfs(int)':
dreaming.cpp:23:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for (auto [v, w] : graf[u])
      |            ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10976 KB Output is correct
2 Incorrect 15 ms 10980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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