oj.uz

Submission #1087532

# Submission time Handle Problem Language Result Execution time Memory
1087532 2024-09-12T21:06:50 Z vincentbucourt1 Tropical Garden (IOI11_garden) C++14
49 / 100
 76 ms 46164 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 < 31; 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[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][1];
			revAdj[adj[i + V]].push_back(i + V);
		}
	}

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

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

	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
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14680 KB Output is correct
2 Correct 8 ms 14688 KB Output is correct
3 Correct 6 ms 14936 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 8 ms 14940 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14680 KB Output is correct
2 Correct 8 ms 14688 KB Output is correct
3 Correct 6 ms 14936 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 8 ms 14940 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 24 ms 22332 KB Output is correct
12 Correct 35 ms 27740 KB Output is correct
13 Incorrect 76 ms 46164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14680 KB Output is correct
2 Correct 8 ms 14688 KB Output is correct
3 Correct 6 ms 14936 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 14684 KB Output is correct
9 Correct 8 ms 14940 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 24 ms 22332 KB Output is correct
12 Correct 35 ms 27740 KB Output is correct
13 Incorrect 76 ms 46164 KB Output isn't correct
14 Halted 0 ms 0 KB -