#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int MAX_N = 2*1e5;
int bl[2*MAX_N][30];
int max_p[MAX_N];
vector<vector<pii>> adj;
int target;
int n;
int dfs(int u, vector<int>& vis, int d){
////cout<<"dfs "<<u<<" "<<u%n<<" "<<u/n<<endl;
vis[u] =d;
if(vis[bl[u][0]] == -1){
return dfs(bl[u][0], vis, d+1);
}
else{
if(bl[u][0] == target){
return d+1;
}
else{
return -1;
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n =N;
adj.resize(N);
for(int i = 0; i <M; i++){
adj[R[i][0]].push_back(pii(i, R[i][1]));
adj[R[i][1]].push_back(pii(i, R[i][0]));
}
for(int i = 0; i<N; i++){
max_p[i] = adj[i][0].first;
}
for(int i = 0; i<N; i++){
bl[i][0] = adj[i][0].second;
if(adj[i][0].first == max_p[adj[i][0].second]){
bl[i][0] += N;
}
if(adj[i].size()>1){
bl[i+N][0] = adj[i][1].second;
if(adj[i][1].first == max_p[adj[i][1].second]){
bl[i+N][0] += N;
}
}
else{
bl[i+N][0] = bl[i][0];
}
}
for(int step = 1; step<30; step++){
for(int i = 0; i<2*N; i++){
bl[i][step] = bl[bl[i][step-1]][step-1];
}
}
vector<int> res(Q);
auto calc = [&](){
vector<int> ch(2*N, -1);
int len = dfs(target, ch, 0);
////cout<<endl;
////cout<<len<<endl;
if(len == -1){
map<int, int> oc;
for(int i = 0; i<N; i++){
if(adj[i%N].size()>1 || i<N){
int dist= -1;
if(i == target){
dist = 0;
}
else if(ch[i]!=-1){
dist= -1;
}
else{
int cur = i;
dist = 1;
for(int step = 29; step>=0; step--){
if(ch[bl[cur][step]] == -1){
cur = bl[cur][step];
dist+= (1<<step);
}
}
if(bl[cur][0] == target){
}
else{
dist = -1;
}
}
//cout<<i<<"dist "<<dist<<endl;
if(dist!=-1){
oc[dist] ++;
}
}
}
for(int i = 0; i<Q; i++){
res[i] += oc[G[i]];
}
}
else{
vector<vector<int>> oc(len);
for(int i = 0; i<N; i++){
if(adj[i%N].size()>1 || i<N){
int dist= -1;
if(i == target){
dist = 0;
}
else if(ch[i]!=-1){
dist= len-ch[i];
}
else{
int cur = i;
dist = 1;
for(int step = 29; step>=0; step--){
if(ch[bl[cur][step]] == -1){
cur = bl[cur][step];
dist++;
}
}
if(ch[bl[cur][0]] != -1){
dist += len-ch[bl[cur][0]];
}
else{
dist = -1;
}
}
//cout<<i<<"dist "<<dist<<endl;
if(dist!=-1){
oc[dist%len].push_back(dist);
}
}
}
for(auto e: oc){
sort(e.begin(), e.end());
}
for(int i = 0; i<Q; i++){
int mod = G[i]%len;
int cur =-1;
for(int step = (1<<29); step>0; step/=2){
if(cur+step< oc[mod].size() && oc[mod][cur+step]<=G[i]){
cur+=step;
}
}
res[i]+=cur+1;
}
}
};
target = P;
calc();
target = P+N;
calc();
for(auto e: res){
answer(e);
}
}
Compilation message
garden.cpp: In lambda function:
garden.cpp:162:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | if(cur+step< oc[mod].size() && oc[mod][cur+step]<=G[i]){
| ~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
