#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
#define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
bool cmin(int &a, int b){if(b<a){a=b;return 1;}return 0;}
bool cmax(int &a, int b){if(b>a){a=b;return 1;}return 0;}
void valid(ll in){cout<<((in)?"SI\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
ll gauss(ll n){return (n*(n+1))/2;}
const int N=1e5+5e4+7,INF=1e9;
int dp[N][2],dp2[N][2],done[N][2],vis[N][2],timer=0;
/*
// [0] = tener la minima desocupada, [1] = tener la minima ocupada
dp[u][t]=si yo empiezo en u en estado t en cuantos pasos llego a P en estado [0]
*/
int mn[N],mn2[N];
vii graph[N];
array<int,2> nxt(int u,int t){
int v=((t^1)?mn[u]:(mn2[u]==-1?mn[u]:mn2[u]));
int tv=(mn[v]==u?1:0);
return {v,tv};
}
int dfs(int u,int t, int P){
if(done[u][t])return dp[u][t];
// cout<<u<<" "<<t<<endl;
array<int,2>v=nxt(u,t);
vis[u][t]=timer;
done[u][t]=1;
if(u==P&&t==0)dp[u][t]=0;
else{
if(vis[v[0]][v[1]]==timer){
dp[u][t]=INF;
}else{
dp[u][t]=dfs(v[0],v[1],P);
if(dp[u][t]!=INF)dp[u][t]++;
}
}
return dp[u][t];
}
int dfs2(int u,int t, int P){
if(done[u][t])return dp2[u][t];
// cout<<u<<" "<<t<<endl;
array<int,2>v=nxt(u,t);
vis[u][t]=timer;
done[u][t]=1;
if(u==P&&t==1)dp2[u][t]=0;
else{
if(vis[v[0]][v[1]]==timer){
dp2[u][t]=INF;
}else{
dp2[u][t]=dfs2(v[0],v[1],P);
if(dp2[u][t]!=INF)dp2[u][t]++;
}
}
return dp2[u][t];
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
fo(i,M){
graph[R[i][0]].pb({R[i][1], i});
graph[R[i][1]].pb({R[i][0], i});
}
fo(i,N){
mn[i]=mn2[i]=-1;
int m1=M+1,m2=M+1;
for(auto [v,w]:graph[i]){
if(m1>w)m2=m1,m1=w,mn2[i]=mn[i],mn[i]=v;
else if(m2>w)m2=w,mn2[i]=v;
}
}
fo(i,N){
timer++;
dfs(i,0,P);
timer++;
dfs(i,1,P);
}
fo(i,N)done[i][0]=done[i][1]=0;
fo(i,N){
timer++;
dfs2(i,0,P);
timer++;
dfs2(i,1,P);
}
fo(qi,Q){
int k=G[qi];
int ans=0;
fo(i,N){
if(min(dp[i][0],dp2[i][0])==INF)continue;
int wi,ct;
if(dp[i][0]<dp2[i][0])wi=0,ct=dp[i][0];
else wi=1,ct=dp2[i][0];
if(ct==k)ans++;
else if(ct>k)continue;
else{
int need=k-ct-dp[P][wi];
if(need>=0&&((dp[P][0]>0&&need%dp[P][0]==0)||need==0)){
ans++;continue;
}
need=k-ct-dp2[P][wi];
if(need>=0&&((dp2[P][1]>0&&need%dp2[P][1]==0)||need==0)){
ans++;continue;
}
}
}
answer(ans);
}
}
Compilation message
garden.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O3")
|
garden.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
