oj.uz

답안 #1088074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088074 2024-09-13T19:30:41 Z vincentbucourt1 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 78 ms 69336 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long

const ll INF = 1e9;
const ll MAXN = 2 * 150001;
 
ll V, E, dest;
vector<ll> graph[MAXN];
ll lenMove[MAXN];

ll adj[MAXN];
vector<ll> revAdj[MAXN];
 
ll jump[MAXN][33];
 
ll distGo (ll node, ll len) {
	for (ll i = 0; i < 33; i++) {
		if (len & (1ll << 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 (ll i = 0; i < Q; i++) {
		lenMove[i] = G[i];
	}
 
	for (ll i = 0; i < E; i++) {
		graph[R[i][0]].push_back(R[i][1]);
		graph[R[i][1]].push_back(R[i][0]);
	}
 
	for (ll 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 (ll 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 (ll i = 0; i < 2*V; i++) {
		jump[i][0] = adj[i];
	}
 
	for (ll i = 1; i < 33; i++) {
		for (ll node = 0; node < 2*N; node++) {
			jump[node][i] = jump[jump[node][i-1]][i-1];
		}
	}
 
	ll endOn;
	ll ans;
	for (ll q = 0; q < Q; q++) {
		ans = 0;
		for (ll 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 7 ms 14936 KB Output is correct
2 Correct 7 ms 14940 KB Output is correct
3 Correct 7 ms 15108 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 7 ms 15196 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 8 ms 15452 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14936 KB Output is correct
2 Correct 7 ms 14940 KB Output is correct
3 Correct 7 ms 15108 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 7 ms 15196 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 8 ms 15452 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 23 ms 28764 KB Output is correct
12 Correct 43 ms 38560 KB Output is correct
13 Incorrect 78 ms 69336 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14936 KB Output is correct
2 Correct 7 ms 14940 KB Output is correct
3 Correct 7 ms 15108 KB Output is correct
4 Correct 6 ms 14428 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 7 ms 15196 KB Output is correct
7 Correct 7 ms 14428 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 8 ms 15452 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 23 ms 28764 KB Output is correct
12 Correct 43 ms 38560 KB Output is correct
13 Incorrect 78 ms 69336 KB Output isn't correct
14 Halted 0 ms 0 KB -