#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)+3;
struct state{
int u,t;
state(){}
state(int u,int t):u(u),t(t){}
};
int mn[N],mn2[N];
state 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};
}
state nxt(state e){
int u=e.u,t=e.t;
int v=((t^1)?mn[u]:(mn2[u]==-1?mn[u]:mn2[u]));
int tv=(mn[v]==u?1:0);
return {v,tv};
}
vii graph1[N];
vector<state> graphinv[N][2];
int md1[N][2],md2[N][2], vis[N][2],timer=0;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
fo(i,N)graph1[i].clear(),graphinv[i][0].clear(),graphinv[i][1].clear();
fo(i,M){
graph1[R[i][0]].pb({R[i][1], i});
graph1[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]:graph1[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){
fo(j,2){
state nx=nxt(i,j);
graphinv[nx.u][nx.t].pb(state(i,j));
md1[i][j]=md2[i][j]=INF;
}
}
queue<state>q;
q.push(state(P, 0));
md1[P][0]=0;
while(sz(q)){
state u=q.front();q.pop();
for(state v:graphinv[u.u][u.t]){
if(md1[v.u][v.t]==INF){
md1[v.u][v.t]=md1[u.u][u.t]+1;
q.push(v);
}
}
}
q.push(state(P, 1));
md2[P][1]=0;
while(sz(q)){
state u=q.front();q.pop();
for(state v:graphinv[u.u][u.t]){
if(md2[v.u][v.t]==INF){
md2[v.u][v.t]=md2[u.u][u.t]+1;
q.push(v);
}
}
}
timer++;
int toP0=0,toP1=0;
state act={P,0};
toP0++;
act=nxt(act);
while(act.u!=P||act.t!=0){
vis[act.u][act.t]=timer;
toP0++;
act=nxt(act);
if(vis[act.u][act.t]==timer){
toP0=INF;
break;
}
}
act={P,1};
toP1++;
act=nxt(act);
timer++;
while(act.u!=P||act.t!=0){
vis[act.u][act.t]=timer;
toP1++;
act=nxt(act);
if(vis[act.u][act.t]==timer){
toP1=INF;
break;
}
}
// cout<<toP0<<" "<<toP1<<endl;
fo(qi,Q){
int k=G[qi];
int ans=0;
fo(i,N){
// acabar en el state(P, 0)
if(md1[i][0]<=k&&(k-md1[i][0])%toP0==0){
ans++;
continue;
}
if(md2[i][0]<=k&&(k-md2[i][0])%toP1==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")
|
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:72:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for(auto [v,w]:graph1[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
