oj.uz

답안 #1087532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -