oj.uz

Submission #1087527

# Submission time Handle Problem Language Result Execution time Memory
1087527 2024-09-12T20:41:31 Z vincentbucourt1 Tropical Garden (IOI11_garden) C++14
0 / 100
 6 ms 14680 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second

const int INF = 1e9;
const int MAXN = 2 * 150001;

int V, E, dest;
vector<int> graph[MAXN];
int lenMove[MAXN];

int adj[MAXN];
vector<int> revAdj[MAXN];

int jump[MAXN][32];

int distGo (int node, int len) {
	for (int i = 0; i < 32; i++) {
		if (len & (1 << i)) {
			node = jump[node][i];
		}
	}
	return node;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {

	V = N, E = M, dest = P;
	for (int i = 0; i < Q; i++) {
		lenMove[i] = G[i];
	}

	for (int i = 0; i < E; i++) {
		graph[R[i][0]].push_back(R[i][1]);
		graph[R[i][1]].push_back(R[i][0]);
	}

	for (int i = 0; i < V; i++) {
		if (graph[i].size() > 1 && graph[graph[i][0]][0] == i) {
			adj[i] = graph[i][0] + V;
			revAdj[adj[i]].push_back(i);
		}
		else {
			adj[i] = graph[i][0];
			revAdj[adj[i]].push_back(i);
		}
	}

	for (int i = 0; i < V; i++) {
		if (graph[i].size() > 1 && graph[graph[i][1]][0] == i) {
			adj[i + V] = graph[i][1] + V;
			revAdj[adj[i + V]].push_back(i + V);
		}
		else if (graph[i].size() == 1 && graph[graph[i][0]][0] == i) {
			adj[i + V] = graph[i][0] + V;
			revAdj[adj[i + V]].push_back(i + V);
		}
		else {
			adj[i + V] = graph[i][0];
			revAdj[adj[i + V]].push_back(i + V);
		}
	}

	for (int i = 0; i < 2*V; i++) {
		jump[i][0] = adj[i];
	}

	for (int node = 0; node < 2*V; node++) {
		for (int i = 1; i < 32; i++) {
			jump[node][i] = jump[jump[node][i-1]][i-1];
		}
	}

	cout << adj[8] << "\n";

	int endOn;
	int ans;
	for (int q = 0; q < Q; q++) {
		ans = 0;
		for (int node = 0; node < V; node++) {
			endOn = distGo(node, lenMove[q]);
			if (endOn == dest || endOn == dest+V) {
				ans++;
			}
		}
		answer(ans);
	}
}

Subtask #1
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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