Submission #839833

#	Time	Username	Problem	Language	Result	Execution time	Memory
839833		Mohmad_Zaid	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	93 ms	4308 KiB

dungeons

// #include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int N;
vector<int>strength,power,win,lose;
vector<int>pre_process;
vector<bool>vis;
int dfs(int node){
    if(vis[node])return pre_process[node];
    vis[node]=1;
    if(node!=N){
        pre_process[node]=1+dfs(win[node]);
    }
    return pre_process[node];
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N=n;
    pre_process.resize(n+1,0);
    vis.assign(n+1,0);
    strength=s;
    power=p;
    win=w;
    lose=l;
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        dfs(i);
    }
    // for(int i=0;i<n;i++){
    //     cout<<pre_process[i];
    // }
    return;
}

ll simulate(int x, int z) {
    ll ans=z;
    vis.assign(N+1,0);
    ll pre=0;
    while(ans<strength[0]){
        // cout<<ans<<endl;
        if(x==N){
            return ans;
        }
        if(vis[x]){
            ll sum=0;
            // cout<<"x: "<<x<<endl;
            sum+=power[x];
            int hi=lose[x];
            while(hi!=x){
                sum+=power[hi];
                hi=lose[hi];
            }
            ans=z;
            ll more;
            more=pre-sum;
            // cout<<"hi: "<<hi<<endl;
            // cout<<"pre: "<<pre<<endl;
            // cout<<"more: "<<more<<endl;
            // cout<<"sum: "<<sum<<endl;
            ans+=more;
            ll rounds;
            rounds=((strength[0]-more)/(sum))*sum;
            // cout<<"rounds: "<<rounds<<endl;
            ans+=rounds;
            sum=0;
            while(sum<(strength[0]-(rounds+(more)))){
                sum+=power[hi];
                hi=lose[hi];
            }
            ans+=sum;
            // cout<<"sum2: "<<sum<<endl;
            // cout<<"ans: "<<ans<<endl;
            x=hi;
            break;
        }
        ans+=power[x];
        // if(ans>=strength[0])break;
        pre+=power[x];
        vis[x]=1;
        x=lose[x];
    }
    // cout<<x<<endl;
    ans+=(pre_process[x]*1LL)*strength[0];
    return ans;
}
// int main(){
//     int n=4,q=2;
//     vector<int>s(n),p(n),w(n),l(n);
//     for(int i=0;i<n;i++)cin>>s[i];
//     for(int i=0;i<n;i++)cin>>p[i];
//     for(int i=0;i<n;i++)cin>>w[i];
//     for(int i=0;i<n;i++)cin>>l[i];
//     // vector<int>s={8,8,8,8},p={1,2,1,3},w={3,2,3,4},l={1,3,1,0};
//     init(n,s,p,w,l);
//     cout<<simulate(1,0)<<endl;
// }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11