oj.uz

Submission #881986

# Submission time Handle Problem Language Result Execution time Memory
881986 2023-12-02T11:33:28 Z serifefedartar Dreaming (IOI13_dreaming) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 21;
const ll MAXN = 1e5 + 10000;

vector<vector<pair<int,int>>> graph;
int vis[MAXN], up[MAXN], mx[MAXN];
pair<int,int> st[MAXN];
int dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		int Q = u.s + dfs(u.f, node);
		if (Q > st[node].f)
			st[node] = {Q, st[node].f};
		else if (Q > st[node].s)
			st[node] = {st[node].f, Q};
	}
	return st[node].f;
}

void dfs2(int node, int parent, int par_len) {
	vis[node] = true;
	if (node != parent) {
		int th = st[node].f + par_len;
		up[node] = up[parent] + par_len;
		if (th == st[parent].f)
			up[node] = max(up[node], st[parent].s + par_len);
		else
			up[node] = max(up[node], st[parent].f + par_len);
	}
	mx[node] = max(up[node], st[node].f);

	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs2(u.f, node, u.s);
	}
}

int mx_node = 0, mx_dist = -1;
void dfs3(int node, int parent, int dist) {
	if (dist > mx_dist) {
		mx_dist = dist;
		mx_node = node;
	}

	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs3(u.f, node, dist + u.s);
	}
}

int diameter(int node) {
	mx_dist = -1, mx_node = 0;
	dfs3(node, node, 0);
	int q = mx_node;
	dfs3(q, q, 0);
	return mx_dist;
}

int nd = 0;
void dfs4(int node, int parent) {
	vis[node] = true;
	if (mx[node] > nd)
		nd = mx[node];
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs4(u.f, node);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 0; i < M; i++) {
		graph[A[i]].push_back({B[i], T[i]});
		graph[B[i]].push_back({A[i], T[i]});
	}

	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			dfs(i, i);
			dfs2(i, i, 0);
		}
	}

	for (int i = 1; i <= N; i++)
		vis[i] = false;
	priority_queue<pair<int,int>, greater<pair<int,int>>, vector<pair<int,int>>> pq;
	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			int dia = diameter(i);
			nd = 0;
			dfs4(i, i);
			pq.push({nd, dia});
		}
	}

	while (pq.size() >= 2) {
		pair<int,int> A = pq.top();
		pq.pop();
		pair<int,int> B = pq.top();
		pq.pop();
		
		int new_dia = max(A.s, max(B.s, A.f + B.f + L));
		int new_mx = min(max(A.f, B.f + L), max(A.f + L, B.f));
		pq.push({new_mx, new_dia});
	}

	return pq.top().s;
}

Compilation message

In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_queue.h: In instantiation of 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >':
dreaming.cpp:98:79:   required from here
/usr/include/c++/10/bits/stl_queue.h:480:67: error: no type named 'value_type' in 'struct std::greater<std::pair<int, int> >'
  480 |       static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
      |                                                                   ^~~~~
/usr/include/c++/10/bits/stl_queue.h:486:47: error: no type named 'value_type' in 'struct std::greater<std::pair<int, int> >'
  486 |       typedef typename _Sequence::value_type  value_type;
      |                                               ^~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:487:46: error: no type named 'reference' in 'struct std::greater<std::pair<int, int> >'
  487 |       typedef typename _Sequence::reference  reference;
      |                                              ^~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:488:51: error: no type named 'const_reference' in 'struct std::greater<std::pair<int, int> >'
  488 |       typedef typename _Sequence::const_reference const_reference;
      |                                                   ^~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:489:46: error: no type named 'size_type' in 'struct std::greater<std::pair<int, int> >'
  489 |       typedef typename _Sequence::size_type  size_type;
      |                                              ^~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:104:7: error: 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >' has no member named 'push'
  104 |    pq.push({nd, dia});
      |       ^~~~
dreaming.cpp:108:12: error: 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >' has no member named 'size'
  108 |  while (pq.size() >= 2) {
      |            ^~~~
dreaming.cpp:109:24: error: 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >' has no member named 'top'; did you mean 'pop'?
  109 |   pair<int,int> A = pq.top();
      |                        ^~~
      |                        pop
dreaming.cpp:111:24: error: 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >' has no member named 'top'; did you mean 'pop'?
  111 |   pair<int,int> B = pq.top();
      |                        ^~~
      |                        pop
dreaming.cpp:116:6: error: 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >' has no member named 'push'
  116 |   pq.push({new_mx, new_dia});
      |      ^~~~
dreaming.cpp:119:12: error: 'class std::priority_queue<std::pair<int, int>, std::greater<std::pair<int, int> >, std::vector<std::pair<int, int> > >' has no member named 'top'; did you mean 'pop'?
  119 |  return pq.top().s;
      |            ^~~
      |            pop
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from dreaming.cpp:1:
/usr/include/c++/10/bits/stl_queue.h: In instantiation of 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::pair<int, int>; _Sequence = std::greater<std::pair<int, int> >; _Compare = std::vector<std::pair<int, int> >]':
dreaming.cpp:110:10:   required from here
/usr/include/c++/10/bits/stl_queue.h:678:18: error: 'struct std::greater<std::pair<int, int> >' has no member named 'begin'
  678 |  std::pop_heap(c.begin(), c.end(), comp);
      |                ~~^~~~~
/usr/include/c++/10/bits/stl_queue.h:678:29: error: 'struct std::greater<std::pair<int, int> >' has no member named 'end'
  678 |  std::pop_heap(c.begin(), c.end(), comp);
      |                           ~~^~~
/usr/include/c++/10/bits/stl_queue.h:679:4: error: 'struct std::greater<std::pair<int, int> >' has no member named 'pop_back'
  679 |  c.pop_back();
      |  ~~^~~~~~~~