oj.uz

Submission #762709

# Submission time Handle Problem Language Result Execution time Memory
762709 2023-06-21T16:35:55 Z MarwenElarbi Fun Tour (APIO20_fun) C++17
26 / 100
 92 ms 16576 KB 
#include <bits/stdc++.h>
#include "fun.h"
#define pb push_back
#define ll long long
#define fi first
#define se second
using namespace std;
const int MOD=1e9+7;
const int nax=1e5+5;




/*static void wrongAnswer(std::string message) {
  printf("WA: %s\n", message.c_str());
  exit(0);
}

namespace tree_helper {

static int N;
static int logN;
static std::vector<std::vector<int>> parent;
static std::vector<int> depth;
static std::vector<int> subtree_size;

static void dfs(
    const std::vector<std::vector<int>>& adj_list,
    int current_node, int parent_node) {
  parent[0][current_node] = parent_node;
  subtree_size[current_node] = 1;
  for (int i = 0; i < static_cast<int>(adj_list[current_node].size()); ++i) {
    const int next_node = adj_list[current_node][i];
    if (next_node != parent_node) {
      depth[next_node] = depth[current_node] + 1;
      dfs(adj_list, next_node, current_node);
      subtree_size[current_node] += subtree_size[next_node];
    }
  }
}

static void initializeTree(const std::vector<std::vector<int>>& adj_list) {
  N = static_cast<int>(adj_list.size());

  depth = std::vector<int>(N, 0);
  subtree_size = std::vector<int>(N, 0);
  for (logN = 0; (1 << logN) < N; ++logN) {}
  parent = std::vector<std::vector<int>>(logN, std::vector<int>(N, 0));

  dfs(adj_list, 0, 0);
  for (int i = 1; i < logN; ++i) {
    for (int j = 0; j < N; ++j) {
      parent[i][j] = parent[i - 1][parent[i - 1][j]];
    }
  }
}

static int getLowestCommonAncestor(int X, int Y) {
  if (depth[X] < depth[Y]) {
    std::swap(X, Y);
  }
  for (int i = logN - 1; i >= 0; --i) {
    if (depth[parent[i][X]] >= depth[Y]) {
      X = parent[i][X];
    }
  }
  if (X == Y) {
    return X;
  }
  for (int i = logN - 1; i >= 0; --i) {
    if (parent[i][X] != parent[i][Y]) {
      X = parent[i][X];
      Y = parent[i][Y];
    }
  }
  return parent[0][X];
}

static int getDistance(int X, int Y) {
  return depth[X] + depth[Y] - 2 * depth[getLowestCommonAncestor(X, Y)];
}

static int attractionsBehind(int X, int Y) {
  if (X == Y) {
    return N;
  }
  for (int i = logN - 1; i >= 0; --i) {
    if (depth[parent[i][X]] > depth[Y]) {
      X = parent[i][X];
    }
  }
  if (Y == parent[0][X]) {
    return N - subtree_size[X];
  }
  return subtree_size[Y];
}

static void checkFunTour(const std::vector<int>& fun_tour) {
  if (static_cast<int>(fun_tour.size()) != N) {
    wrongAnswer("Invalid size");
  }

  std::vector<bool> visited_attractions(N, false);
  for (int i = 0; i < N; ++i) {
    if (fun_tour[i] < 0 || fun_tour[i] >= N) {
      wrongAnswer("Invalid index");
    }
    if (visited_attractions[fun_tour[i]]) {
      wrongAnswer("Repeated index");
    }
    visited_attractions[fun_tour[i]] = true;
  }

  int last_travel_time = getDistance(fun_tour[0], fun_tour[1]);
  for (int i = 2; i < N; ++i) {
    int travel_time = getDistance(fun_tour[i - 1], fun_tour[i]);
    if (travel_time > last_travel_time) {
      wrongAnswer("Tour is not fun");
    }
    last_travel_time = travel_time;
  }
}

}*/ // namespace tree_helper

vector<int> tab;
vector<int> adj[nax];
vector<bool> vis(nax);
pair<int,int> dp[nax];
int sec;
int mx;
int fir; 
/*int hoursRequired(int X, int Y) {
  if (--Q < 0) {
    wrongAnswer("Too many queries");
  }
  if (X < 0 || X >= N || Y < 0 || Y >= N) {
    wrongAnswer("Invalid index");
  }
  return tree_helper::getDistance(X, Y);
}

int attractionsBehind(int X, int Y) {
  if (--Q < 0) {
    wrongAnswer("Too many queries");
  }
  if (X < 0 || X >= N || Y < 0 || Y >= N) {
    wrongAnswer("Invalid index");
  }
  return tree_helper::attractionsBehind(X, Y);
}*/
vector<int> createFunTour(int n, int q){
	int m=0;
	mx=-1;
	for (int i = 1; i < n; ++i)
	{
		int cur=hoursRequired(0, i);
		if (cur>mx){
			mx=cur;
			fir=i;
		}
	}
	while(m<n){
		tab.pb(fir);
		mx=-1;
		vis[fir]=true;
		int ne;
		for (int i = 0; i < n; ++i)
		{
			if (vis[i]) continue;
			if (i==fir) continue;
			int cur=hoursRequired(fir, i);
			if (cur>mx){
				mx=cur;
				ne=i;
			}
		}
		fir=ne;
		m++;
	}
	return tab;
}
/*int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	assert(2 == scanf("%d %d", &N, &Q));

	  std::vector<std::vector<int>> adj_list(N);
	  for (int i = 0; i < N - 1; ++i) {
	    int A, B;
	    assert(2 == scanf("%d %d", &A, &B));
	    adj_list[A].push_back(B);
	    adj_list[B].push_back(A);
	  }
	  tree_helper::initializeTree(adj_list);

	  std::vector<int> fun_tour = createFunTour(N, Q);
	  tree_helper::checkFunTour(fun_tour);

	  for (int i = 0; i < N; ++i) {
	    printf("%d%c", fun_tour[i], " \n"[i == N - 1]);
	  }
	  return 0;
}*/

Compilation message

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:178:6: warning: 'ne' may be used uninitialized in this function [-Wmaybe-uninitialized]
  178 |   fir=ne;
      |   ~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2672 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2672 KB Output is correct
17 Correct 2 ms 2588 KB Output is correct
18 Correct 1 ms 2672 KB Output is correct
19 Correct 1 ms 2672 KB Output is correct
20 Correct 1 ms 2644 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2672 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2672 KB Output is correct
17 Correct 2 ms 2588 KB Output is correct
18 Correct 1 ms 2672 KB Output is correct
19 Correct 1 ms 2672 KB Output is correct
20 Correct 1 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 1 ms 2672 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 8 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 2 ms 2672 KB Output is correct
27 Correct 2 ms 2668 KB Output is correct
28 Correct 2 ms 2644 KB Output is correct
29 Correct 10 ms 2724 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 3 ms 2644 KB Output is correct
32 Correct 4 ms 2644 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 8 ms 2752 KB Output is correct
35 Correct 9 ms 2724 KB Output is correct
36 Correct 9 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 8 ms 2728 KB Output is correct
39 Correct 4 ms 2644 KB Output is correct
40 Correct 5 ms 2700 KB Output is correct
41 Correct 2 ms 2672 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2672 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2672 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 8 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 9 ms 2672 KB Output is correct
17 Correct 9 ms 2644 KB Output is correct
18 Incorrect 92 ms 16576 KB Too many queries
19 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 10 ms 2724 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 4 ms 2644 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Incorrect 31 ms 2764 KB Too many queries
14 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2672 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2672 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2672 KB Output is correct
17 Correct 2 ms 2588 KB Output is correct
18 Correct 1 ms 2672 KB Output is correct
19 Correct 1 ms 2672 KB Output is correct
20 Correct 1 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 1 ms 2672 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 8 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 2 ms 2672 KB Output is correct
27 Correct 2 ms 2668 KB Output is correct
28 Correct 2 ms 2644 KB Output is correct
29 Correct 10 ms 2724 KB Output is correct
30 Correct 2 ms 2644 KB Output is correct
31 Correct 3 ms 2644 KB Output is correct
32 Correct 4 ms 2644 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 8 ms 2752 KB Output is correct
35 Correct 9 ms 2724 KB Output is correct
36 Correct 9 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 8 ms 2728 KB Output is correct
39 Correct 4 ms 2644 KB Output is correct
40 Correct 5 ms 2700 KB Output is correct
41 Correct 2 ms 2672 KB Output is correct
42 Correct 9 ms 2672 KB Output is correct
43 Correct 9 ms 2644 KB Output is correct
44 Incorrect 92 ms 16576 KB Too many queries
45 Halted 0 ms 0 KB -