#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define mxn 300005
#include "garden.h"
#include "gardenlib.h"
//#define answer(x) cout<<x<<'\n';
using namespace std;
struct International_Olympiad_in_Informatics
{
priority_queue <int,vector <int>,greater <int> > heap;
vector <int> a[mxn],child[mxn],changed,in4[mxn];
int n,m,d[mxn],incycle[mxn],sz[mxn],h[mxn],cnt[mxn],finish,student,U[mxn],V[mxn],res[mxn],step,Turn[mxn],nxt[mxn],i,w[mxn],u,v;
struct query { int k,pos; } q[mxn];
void dfs(int u)
{
sz[u]=1;
for(int v:child[u])
if(incycle[v]==0) h[v]=h[u]+1,dfs(v),sz[u]+=sz[v];
}
int rev(int u) { return (u<=m) ? u+m : u-m; }
void DFS(int u)
{
int x=0;
for(int v:child[u])
if(incycle[v]==0 && sz[x]<sz[v]) x=v;
for(int v:child[u])
if(incycle[v]==0 && v!=x)
{
DFS(v);
in4[v]=changed;
for(int x:changed) cnt[x]=0;
changed.clear();
}
if(x>0) DFS(x);
if(d[u]) cnt[h[u]]++,changed.push_back(h[u]);
for(int v:child[u])
if(incycle[v]==0 && v!=x)
for(int x:in4[v]) cnt[x]++,changed.push_back(x);
// if(V[u]==finish) cerr<<U[u]<<" "<<V[u]<<'\n';
if(V[u]==finish && incycle[u]==0)
{
// cerr<<u<<'\n';
for(int i=1;i<=student;i++)
if(q[i].k+h[u]<=2*m) res[q[i].pos]+=cnt[q[i].k+h[u]];
}
}
void DFS_add(int u,int i)
{
if(d[u]) heap.push(h[u]-i);
for(int v:child[u])
if(incycle[v]==0) DFS_add(v,i);
}
void Find_cycle(int u)
{
step++;
// cerr<<U[u]<<" "<<V[u]<<'\n';
vector <int> cycle;
while(1)
{
// cerr<<u<<'\n';
Turn[u]=step;
int v=nxt[u];
if(Turn[v]==0) u=v;
else if(Turn[v]<step) return ;
else
{
while(v!=u) cycle.push_back(v),v=nxt[v];
cycle.push_back(u);
break;
}
}
for(int u:cycle) incycle[u]=1;
for(int u:cycle) dfs(u),DFS(u);
for(int i=0;i<cycle.size();i++)
{
int u=cycle[i];
if(V[u]==finish)
{
// cerr<<U[u]<<" "<<V[u]<<'\n';
memset(cnt,0,sizeof(cnt));
while(heap.size()>0) heap.pop();
for(int j=0;j<=i;j++) DFS_add(cycle[j],j);
for(int inq=1;inq<=student;inq++)
{
while(heap.size()>0 && i+heap.top()<=q[inq].k)
{
cnt[(i+heap.top())%cycle.size()]++;
heap.pop();
}
// cerr<<cnt[q[inq].k%cycle.size()]<<'\n';
res[q[inq].pos]+=cnt[q[inq].k%cycle.size()];
}
memset(cnt,0,sizeof(cnt));
while(heap.size()>0) heap.pop();
for(int j=(int)cycle.size()-1;j>i;j--) DFS_add(cycle[j],j);
for(int inq=1;inq<=student;inq++)
{
while(heap.size()>0 && i+cycle.size()+heap.top()<=q[inq].k)
{
cnt[(i+cycle.size()+heap.top())%cycle.size()]++;
heap.pop();
}
// cerr<<cnt[q[inq].k%cycle.size()]<<'\n';
res[q[inq].pos]+=cnt[q[inq].k%cycle.size()];
}
}
}
}
void Work(int _n,int _m,int _p,int _r[][2],int _q,int _g[])
{
n=_n; m=_m; finish=_p; student=_q;
for(i=1;i<=m;i++) U[i]=_r[i][0],V[i]=_r[i][1];
for(i=1;i<=student;i++) _g[i]--,q[i]={ _g[i],i };
sort(q+1,q+student+1,[&](query a,query b){ return a.k<b.k; });
/////////////////////////////////////////////////////////////////////////
for(i=1;i<=m;i++)
{
w[i]=i;
a[U[i]].push_back(i); a[V[i]].push_back(i+m);
V[i+m]=U[i]; U[i+m]=V[i]; w[i+m]=w[i];
}
for(u=1;u<=n;u++) sort(a[u].begin(),a[u].end(),[&](int i,int j){ return w[i]<w[j]; });
for(i=1;i<=2*m;i++)
{
u=U[i]; v=V[i];
if(a[v].size()==1) nxt[i]=rev(i);
else nxt[i]=a[v][a[v][0]==rev(i)];
d[i]=(a[u][0]==i);
// if(a[v].size()==1) cerr<<v<<'\n';
// cerr<<i<<" "<<nxt[i]<<'\n';
// if(V[i]==finish) cerr<<i<<'\n';
}
for(u=1;u<=2*m;u++) child[nxt[u]].push_back(u);
for(u=1;u<=2*m;u++)
if(Turn[u]==0) Find_cycle(u);
}
} IOI;
/*
Write a procedure count_routes(N,M,P,R,Q,G) that takes the following parameters:
N – the number of fountains. The fountains are numbered 0 through N-1.
• M– the number of trails. The trails are numbered 0 through M-1. The trails will be given
in decreasing order of beauty: for 0 ≤ i < M-1, trail i is more beautiful than trail i+1.
• P – the fountain at which the premium restaurant is located.
• R – a two-dimensional array representing the trails. For 0 ≤ i < M, trail i connects the
fountains R[i][0] and R[i][1]. Recall that each trail joins a pair of distinct fountains, and
no two trails join the same pair of fountains.
• Q – the number of groups of students.
• G – a one-dimensional array of integers containing the values of K. For 0 ≤ i < Q, G[i] is
the number of trails K that the i-th group will take. */
void count_routes(int n,int m,int p,int r[][2],int q,int g[])
{
p++;
for(int i=m;i>=1;i--) r[i][0]=r[i-1][0],r[i][1]=r[i-1][1],r[i][0]++,r[i][1]++;
for(int i=q;i>=1;i--) g[i]=g[i-1];
IOI.Work(n,m,p,r,q,g);
for(int i=0;i<q;i++) answer(IOI.res[i+1]);
}
/*
int n,m,p,i,r[mxn][2],g[mxn],q;
int main()
{
freopen("garden.inp","r",stdin);
freopen("garden.out","w",stdout);
cin>>n>>m>>p;
for(i=0;i<m;i++) cin>>r[i][0]>>r[i][1];
cin>>q;
for(i=0;i<q;i++) cin>>g[i];
count_routes(n,m,p,r,q,g);
}
*/
Compilation message
garden.cpp: In member function 'void International_Olympiad_in_Informatics::Find_cycle(int)':
garden.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<cycle.size();i++)
| ~^~~~~~~~~~~~~
garden.cpp:110:69: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
110 | while(heap.size()>0 && i+cycle.size()+heap.top()<=q[inq].k)
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
35676 KB |
Output is correct |
| 2 |
Correct |
7 ms |
35420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
35672 KB |
Output is correct |
| 4 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 5 |
Correct |
7 ms |
35420 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
35736 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
35676 KB |
Output is correct |
| 2 |
Correct |
7 ms |
35420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
35672 KB |
Output is correct |
| 4 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 5 |
Correct |
7 ms |
35420 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
35736 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
35676 KB |
Output is correct |
| 2 |
Correct |
7 ms |
35420 KB |
Output is correct |
| 3 |
Correct |
8 ms |
35672 KB |
Output is correct |
| 4 |
Correct |
6 ms |
35420 KB |
Output is correct |
| 5 |
Correct |
7 ms |
35420 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
35736 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
