oj.uz

Submission #1088074

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -