#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>;
using namespace std;
#define st first
#define nd second
#define pb push_back
using pii = pair<int, int>;
using vi = vector<int>;
void count_routes(int n, int m, int p, int edg[][2], int q, int QQ[])
{
vector<pii> E[n][2];
int naj[n][2], co[n][2], dist[n][2], typ[n][2];
for(int i=0; i<n; i++){
naj[i][0]=naj[i][1]=1e9;
}
for(int i=m-1; i>=0; i--){
naj[edg[i][0]][0]=i;
co[edg[i][0]][0]=edg[i][1];
naj[edg[i][1]][0]=i;
co[edg[i][1]][0]=edg[i][0];
}
for(int i=m-1; i>=0; i--){
if(naj[edg[i][0]][0]!=i){
naj[edg[i][0]][1]=i;
co[edg[i][0]][1]=edg[i][1];
}
if(naj[edg[i][1]][0]!=i){
naj[edg[i][1]][1]=i;
co[edg[i][1]][1]=edg[i][0];
}
}
for(int i=0; i<n; i++){
dist[i][0]=dist[i][1]=1e9;
if(naj[i][1]==1e9){
naj[i][1]=naj[i][0];
co[i][1]=co[i][0];
}
cerr<<i<<" "<<naj[i][0]<<" "<<co[i][0]<<" "<<naj[i][1]<<" "<<co[i][1]<<"\n";
E[co[i][0]][(naj[i][0]==naj[co[i][0]][0])].pb({i, 0});
E[co[i][1]][(naj[i][1]==naj[co[i][1]][0])].pb({i, 1});
}
vector<pii> V;
for(int i=0; i<n; i++){
if(co[i][0]==p){
V.pb({i, 0});
dist[i][0]=1;
typ[i][0]=(naj[i][0]==naj[p][0]);
}
if(co[i][1]==p){
V.pb({i, 1});
dist[i][1]=1;
typ[i][1]=(naj[i][1]==naj[p][0]);
}
}
for(int i=0; i<n; i++){
for(int j=0; j<2; j++){
cerr<<i<<" "<<j<<": ";
for(pii e:E[i][j]){
cerr<<"{"<<e.st<<", "<<e.nd<<"} ";
}
cerr<<"\n";
}
}
for(int i=0; i<V.size(); i++){
cerr<<V[i].st<<" "<<V[i].nd<<"\n";
for(pii e:E[V[i].st][V[i].nd]){
if(dist[e.st][e.nd]!=1e9)continue;
V.pb(e);
typ[e.st][e.nd]=typ[V[i].st][V[i].nd];
dist[e.st][e.nd]=dist[V[i].st][V[i].nd]+1;
}
}
vector<vector<int> > cykle;
vector<pair<int, int> > eve;
vector<int> eve2;
for(int i=0; i<n; i++){
for(int j=0; j<1; j++){
if(dist[i][j]!=1e9){
cerr<<i<<" "<<j<<" "<<dist[i][j]<<" "<<typ[i][j]<<": ";
if(dist[p][typ[i][j]]==1e9){
eve2.pb(dist[i][j]);
cerr<<dist[i][j]<<"\n";
}
else{
if(typ[p][typ[i][j]]==typ[i][j]){
eve.pb({dist[i][j], dist[p][typ[i][j]]});
cerr<<"{"<<dist[i][j]<<", "<<dist[p][typ[i][j]]<<"}\n";
}
else{
if(dist[p][typ[i][j]^1]==1e9){
eve2.pb(dist[i][j]);
eve2.pb(dist[i][j]+dist[p][typ[i][j]]);
cerr<<dist[i][j]<<" "<<dist[i][j]+dist[p][typ[i][j]]<<"\n";
}
else{
eve.pb({dist[i][j], dist[p][0]+dist[p][1]});
eve.pb({dist[i][j]+dist[p][typ[i][j]], dist[p][0]+dist[p][1]});
cerr<<"{"<<dist[i][j]<<", "<<dist[p][typ[i][j]]<<"}";
cerr<<"{"<<dist[i][j]+dist[p][typ[i][j]]<<", "<<dist[p][0]+dist[p][1]<<"}\n";
}
}
}
}
}
}
sort(eve.begin(), eve.end());
sort(eve2.begin(), eve2.end());
reverse(eve.begin(), eve.end());
reverse(eve2.begin(), eve2.end());
vector<pii> Q(q);
vector<int> ans(q);
for(int i=0; i<q; i++){
Q[i].st=QQ[i];
Q[i].nd=i;
}
sort(Q.begin(), Q.end());
for(pii ii:Q){
int i=ii.st, qq=ii.nd;
while(eve2.size() && eve2.back()<i)eve2.pop_back();
while(eve2.size() && eve2.back()==i)eve2.pop_back(), ans[qq]++;
while(eve.size() && eve.back().st<=i){
if(cykle.size()>0 && cykle[0].size()==eve.back().nd){
cykle[0][eve.back().st%eve.back().nd]++;
}
else if(cykle.size()>1 && cykle[1].size()==eve.back().nd){
cykle[1][eve.back().st%eve.back().nd]++;
}
else{
cykle.pb(vi(eve.back().nd));
cykle.back()[eve.back().st%eve.back().nd]++;
}
eve.pop_back();
}
if(cykle.size()>0)ans[qq]+=cykle[0][i%cykle[0].size()];
if(cykle.size()>1)ans[qq]+=cykle[1][i%cykle[1].size()];
}
for(int i=0; i<q; i++){
answer(ans[i]);
}
}
Compilation message
garden.cpp:3:24: warning: extra tokens at end of #include directive
3 | #include<bits/stdc++.h>;
| ^
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
garden.cpp:124:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
124 | if(cykle.size()>0 && cykle[0].size()==eve.back().nd){
| ^
garden.cpp:127:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | else if(cykle.size()>1 && cykle[1].size()==eve.back().nd){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
468 KB |
Output is correct |
| 2 |
Correct |
48 ms |
608 KB |
Output is correct |
| 3 |
Correct |
49 ms |
508 KB |
Output is correct |
| 4 |
Correct |
3 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
56 ms |
588 KB |
Output is correct |
| 7 |
Correct |
4 ms |
308 KB |
Output is correct |
| 8 |
Correct |
48 ms |
496 KB |
Output is correct |
| 9 |
Correct |
50 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
468 KB |
Output is correct |
| 2 |
Correct |
48 ms |
608 KB |
Output is correct |
| 3 |
Correct |
49 ms |
508 KB |
Output is correct |
| 4 |
Correct |
3 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
56 ms |
588 KB |
Output is correct |
| 7 |
Correct |
4 ms |
308 KB |
Output is correct |
| 8 |
Correct |
48 ms |
496 KB |
Output is correct |
| 9 |
Correct |
50 ms |
600 KB |
Output is correct |
| 10 |
Correct |
4 ms |
340 KB |
Output is correct |
| 11 |
Correct |
700 ms |
5160 KB |
Output is correct |
| 12 |
Correct |
1122 ms |
8352 KB |
Output is correct |
| 13 |
Correct |
4640 ms |
28616 KB |
Output is correct |
| 14 |
Correct |
4524 ms |
30596 KB |
Output is correct |
| 15 |
Execution timed out |
5054 ms |
33504 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
468 KB |
Output is correct |
| 2 |
Correct |
48 ms |
608 KB |
Output is correct |
| 3 |
Correct |
49 ms |
508 KB |
Output is correct |
| 4 |
Correct |
3 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
56 ms |
588 KB |
Output is correct |
| 7 |
Correct |
4 ms |
308 KB |
Output is correct |
| 8 |
Correct |
48 ms |
496 KB |
Output is correct |
| 9 |
Correct |
50 ms |
600 KB |
Output is correct |
| 10 |
Correct |
4 ms |
340 KB |
Output is correct |
| 11 |
Correct |
700 ms |
5160 KB |
Output is correct |
| 12 |
Correct |
1122 ms |
8352 KB |
Output is correct |
| 13 |
Correct |
4640 ms |
28616 KB |
Output is correct |
| 14 |
Correct |
4524 ms |
30596 KB |
Output is correct |
| 15 |
Execution timed out |
5054 ms |
33504 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
