Submission #1042285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042285		vjudge1	Tropical Garden (IOI11_garden)	C++17	100 / 100	946 ms	32620 KiB

garden

#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!=1){
        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){
            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 (stderr)

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")
      |

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31