Submission #1042259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042259		vjudge1	Tropical Garden (IOI11_garden)	C++17	0 / 100	2 ms	8796 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;
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)continue;
                if((dp[P][0]>0&&need%dp[P][0]==0)||need==0){
                    ans++;continue;
                }
                need=k-ct-dp2[P][wi];
                if(need<0)continue;
                if((dp2[P][1]>0&&need%dp2[P][1]==0)||need==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: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31