#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>
#include <utility>
using namespace std;
//void fill_iterated (int N, vector<vector<long long> > &iterated){
//
// for (int i = 1; i < iterated.size(); i++){
//
// for (int n = 0; n < 2 * N; n++){
// iterated[i][n] = iterated[i-1][iterated[i-1][n]];
// }
//
// }
//
//}
//vector<long long> iterate_function (int N, long long applications, vector<vector<long long> > &iterated){
//
//
// vector<long long> function_iterate (2 * N, 0);
//
// for (int i = 0; i < 2 * N; i++){
// function_iterate[i] = i;
// }
//
// for(int i = 0; i < 30; i++){
//
// if (applications & (1 << i)){
//
// for (int j = 0; j < 2 * N; j++){
// function_iterate[j] = iterated[i][function_iterate[j]];
// }
//
// }
//
// }
//
// return function_iterate;
//}
vector<long long> count_preimage(long long N, long long P, int Q, int G[], vector<long long> &vertex_image, vector<vector<long long> > &pre_image){
// cout << endl;
// cout << P << endl;
//
// for (int i = 0; i < 2 * N; i++){
// cout << vertex_image[i] << ' ';
// }
// cout << endl;
vector<long long> results (Q, 0);
vector<bool> visited (2 * N, false);
long long current = vertex_image[P];
long long cycle_length = 0;
while (!visited[current]){
cycle_length++;
visited[current] = true;
current = vertex_image[current];
}
bool is_cycle = false;
if (visited[P]){
is_cycle = true;
}
//cout << "is a cycle: " << is_cycle << ' ' << cycle_length << endl;
if (!is_cycle){
vector<long long> current_pre_image;
current_pre_image.push_back(P);
vector<long long> pre_image_size;
while (current_pre_image.size() != 0){
long long total = 0;
for (int a = 0; a < current_pre_image.size(); a++){
if (current_pre_image[a] < N){
total++;
}
}
pre_image_size.push_back(total);
vector<long long> new_pre_image;
for (int i = 0; i < current_pre_image.size(); i++){
for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
new_pre_image.push_back(pre_image[current_pre_image[i]][j]);
}
}
current_pre_image = new_pre_image;
}
for (int i = 0; i < Q; i++){
if (G[i] >= pre_image_size.size()){
results[i] = 0;
} else {
results[i] = pre_image_size[G[i]];
}
//cout << G[i] << "re" << results[i] << endl;
}
return results;
}
vector<long long> cycle;
long long current1 = P;
for (int i = 0; i < cycle_length; i++){
cycle.push_back(current1);
current1 = vertex_image[current1];
}
vector<long long> pre_image_size (N, 0);
current = vertex_image[P];
int current_offset = cycle_length - 1;
for (int k = 0; k < cycle_length; k++){
vector<long long> current_pre_image;
for (int r = 0; r < pre_image[current].size(); r++){
if (!visited[pre_image[current][r]]){
current_pre_image.push_back(pre_image[current][r]);
}
}
long long counter = 1;
while (current_pre_image.size() != 0){
long long total = 0;
for (int a = 0; a < current_pre_image.size(); a++){
if (current_pre_image[a] < N){
total++;
}
}
pre_image_size[(current_offset + counter)] += total;
vector<long long> new_pre_image;
for (int i = 0; i < current_pre_image.size(); i++){
for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
new_pre_image.push_back(pre_image[current_pre_image[i]][j]);
}
}
current_pre_image = new_pre_image;
}
current = vertex_image[current];
current_offset--;
}
vector<vector<long long> > partial_sums (cycle_length, vector<long long> (N / cycle_length + 1, 0));
for (int i = 0; i < cycle_length; i++){
//cout << 'r' << i << endl;
partial_sums[i][0] = pre_image_size[i];
for (int j = 1; j * cycle_length + i < N; j++){
partial_sums[i][j] = partial_sums[i][j - 1] + pre_image_size[j * cycle_length + i];
}
}
//cout << 'p' << partial_sums[1][0] << endl;
for (int i = 0; i < Q; i++){
long long residue = G[i] % cycle_length;
long long quotient = (G[i] - residue) / cycle_length;
if (G[i] > N){
quotient = partial_sums[residue].size() - 1;
}
results[i] = partial_sums[residue][quotient];
long long pre_cycle = cycle_length - residue;
if (cycle[pre_cycle] < N){
results[i]++;
}
//cout << G[i] << "re" << results[i] << endl;
}
return results;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
vector<long long> vertex_image (2 * N, -1);
//N + i is the trail going to vertex i that goes to i along the most beautiful trail
vector<pair<long long, long long> > best_trail(N, make_pair(M + 1, -1));
for (int i = 0; i < M; i++){
long long s = R[i][0];
long long e = R[i][1];
if (best_trail[s].first > i){
best_trail[s].first = i;
best_trail[s].second = e;
}
if (best_trail[e].first > i){
best_trail[e].first = i;
best_trail[e].second = s;
}
}
vector<pair<long, long> > second_best_trail(N, make_pair(M + 1, -1));
for (int i = 0; i < M; i++){
long long s = R[i][0];
long long e = R[i][1];
if (second_best_trail[s].first > i && i > best_trail[s].first){
second_best_trail[s].first = i;
second_best_trail[s].second = e;
}
if (second_best_trail[e].first > i && i > best_trail[e].first){
second_best_trail[e].first = i;
second_best_trail[e].second = s;
}
}
for (int i = 0; i < N; i++){
//cout << i << ' ' << best_trail[i].first << ' ' << best_trail[i].second << endl;
//cout << second_best_trail[i].first << ' ' << second_best_trail[i].second << endl;
if (second_best_trail[i].second == -1){
second_best_trail[i] = best_trail[i];
}
}
for (int i = 0; i < N; i++){
long long new_fountain = best_trail[i].second;
if (best_trail[i].first == best_trail[new_fountain].first){
vertex_image[i] = new_fountain + N;
} else {
vertex_image[i] = new_fountain;
}
new_fountain = second_best_trail[i].second;
if (second_best_trail[i].first == best_trail[new_fountain].first){
vertex_image[i + N] = new_fountain + N;
} else {
vertex_image[i + N] = new_fountain;
}
}
//target is p or p+N
// for (int i = 0; i < N; i++){
// cout << i << " : " << vertex_image[i] << ' ' << vertex_image[i + N] << endl;
// }
// vector<vector<long long> > iterated (30, vector<long long> (2 * N, 0));
//
// iterated[0] = vertex_image;
//
// fill_iterated(N, iterated);
//
// for (int i = 0; i < 30; i++){
// cout << endl;
// for (int j = 0; j < 2 * N; j++){
// cout << iterated[i][j] << ' ';
// }
// cout << endl << endl;
// }
// vector<long long> function_iterate = iterate_function(N, 3, iterated);
// for (int i = 0; i < 2 * N; i++){
// cout << function_iterate[i] << ' ';
// }
// cout << endl;
vector<vector<long long> > pre_image (2 * N, vector<long long>());
for (int i = 0; i < 2 * N; i++){
pre_image[vertex_image[i]].push_back(i);
}
vector<long long> R1 = count_preimage(N, P, Q, G, vertex_image, pre_image);
vector<long long> R2 = count_preimage(N, P + N, Q, G, vertex_image, pre_image);
for(int i=0; i<Q; i++){
// vector<long long> function_iterate = iterate_function(N, G[i], iterated);
// int total = 0;
// for (int i = 0; i < N; i++){
// if (function_iterate[i] == P || function_iterate[i] == P + N){
// total++;
// }
// }
answer(R1[i] + R2[i]);
}
}
Compilation message
garden.cpp: In function 'std::vector<long long int> count_preimage(long long int, long long int, int, int*, std::vector<long long int>&, std::vector<std::vector<long long int> >&)':
garden.cpp:90:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int a = 0; a < current_pre_image.size(); a++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:99:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < current_pre_image.size(); i++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:100:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (G[i] >= pre_image_size.size()){
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:140:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r = 0; r < pre_image[current].size(); r++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:152:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int a = 0; a < current_pre_image.size(); a++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:161:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < current_pre_image.size(); i++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:162:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < pre_image[current_pre_image[i]].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
