제출 #543309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543309		neki	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	2669 ms	37020 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define ll int
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define par pair<ll, ll>
#define ld long double
#define mod 998244353

void count_routes(ll n, ll m, ll P,ll R[][2], ll Q, ll G[]){
    vc<vc<ll>> edg(n);
    
    loop(i, 0, m){
        edg[R[i][0]].ps(R[i][1]);
        edg[R[i][1]].ps(R[i][0]);
    }
    
    function<ll (ll, ll)> gettip=[&](ll u, ll p){return edg[u].size()>1 && edg[u][0]==p;};
    vc<vc<par>> dp(n, vc<par>(2, make_pair(-2, 0)));
    {
        vc<vc<ll>> act(n, vc<ll>(2, 0));
        ll st=P, pr=-1, cnt=0;
        ll ctip=gettip(st, pr);
        
        dp[P][ctip]=make_pair(-1, 0);
        while(1){
            ll tip=gettip(st, pr);
            
            if(act[st][tip]) break;
            act[st][tip]=1;
            
            ll nst=edg[st][tip];
            pr=st;st=nst;
            ++cnt;
            
            if(st==P){ dp[st][ctip]=make_pair(cnt, gettip(st, pr));break;}
        }
    }
    {
        vc<vc<ll>> act(n, vc<ll>(2, 0));
        ll st=P, pr=edg[P][0], cnt=0;
        ll ctip=gettip(st, pr);
        
        dp[P][ctip]=make_pair(-1, 0);
        while(1){
            ll tip=gettip(st, pr);
            
            if(act[st][tip]) break;
            act[st][tip]=1;
            
            ll nst=edg[st][tip];
            pr=st;st=nst;
            ++cnt;
            
            if(st==P){ dp[st][ctip]=make_pair(cnt, gettip(st, pr));break;}
        }
    }
    {
        vc<vc<ll>> act(n, vc<ll>(2, 0));
        function<par (ll, ll)> dfs=[&](ll u, ll p){
            ll tip=gettip(u, p);
            if(dp[u][tip].fi==-2){
                if(act[u][tip]) dp[u][tip]=make_pair(-1, 0);
                else{
                    act[u][tip]=1;
                    
                    if(edg[u][tip]==P) dp[u][tip]=make_pair(1, gettip(P, u));
                    else{ dp[u][tip]=dfs(edg[u][tip], u); if(dp[u][tip].fi!=-1) ++dp[u][tip].fi;}
                    
                    act[u][tip]=0;
                }
            }
            return dp[u][tip];
        };
        loop(u, 0, n) if(u!=P) dfs(u, -1), dfs(u, edg[u][0]);
    }
    /*loop(u, 0, n){
        loop(tip, 0, 2){cout << dp[u][tip].fi <<" "<< dp[u][tip].se<<" ";}
        cout << endl;
    }*/
    
    loop(qq, 0, Q){
        
        ll ans=0;
        loop(i, 0, n){
            ll ck=G[qq], tip;
            
            if(i==P) tip=0;
            else{
                if(dp[i][0].fi==-1) continue;
                if(ck<dp[i][0].fi) continue;
                
                ck-=dp[i][0].fi;
                tip=dp[i][0].se;
            }
            
            if(ck==0)++ans;
            else if(dp[P][tip].fi==-1);
            else if(dp[P][tip].se==tip) ans+=(ck%dp[P][tip].fi==0);
            else if(dp[P][!tip].fi==-1);
            else if(dp[P][!tip].se==tip){
                ll sk=dp[P][0].fi+dp[P][1].fi;
                if(ck%sk==0 or ck%sk==dp[P][tip].fi)++ans;
            }
            else if(dp[P][!tip].se==(!tip)) ans+=(ck>=dp[P][tip].fi && (ck-dp[P][tip].fi)%dp[P][!tip].fi==0);
        }
        answer(ans);
        //cout << ans<<endl;
    }
}

/*int main(){
    ll R[6][2]={{1, 2},{0, 1},{0, 3},{3, 4},{4, 5},{1, 5}};
    
    ll Q[1]={3};
    count_routes(6, 6, 0, R, 1, Q);
}*/

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