#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>
#include <utility>
#include <queue>
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<int> visited (2 * N, -1);
visited[P] = 0;
bool is_cycle = 0;
long long cycle_length = 0;
queue<long long> to_visit;
to_visit.push(P);
while (!to_visit.empty()){
long long current = to_visit.front();
to_visit.pop();
long long d = visited[current];
for (int i = 0; i < pre_image[current].size(); i++){
if (pre_image[current][i] == P){
is_cycle = true;
cycle_length = d + 1;
} else {
to_visit.push(pre_image[current][i]);
visited[pre_image[current][i]] = d + 1;
}
}
}
for (int i = 0; i < Q; i++){
int total = 0;
for (int n = 0; n < N; n++){
if (is_cycle){
if (G[i] >= visited[n] && (G[i] - visited[n]) % cycle_length == 0){
total++;
}
} else {
if (G[i] == visited[n]){
total++;
}
}
}
results[i] = total;
}
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:78:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < pre_image[current].size(); i++){
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
