Submission #790370

#	Time	Username	Problem	Language	Result	Execution time	Memory
790370		alexander707070	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	20 ms	19740 KiB

dungeons

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 400007
using namespace std;

int n,parent[MAXN],to[MAXN],last,comp[MAXN],x;
int win[MAXN],lose[MAXN],k;
vector<int> v[MAXN];
long long curr,dist[MAXN],pref,minloops,tocomp[MAXN];
int pos[MAXN];

pair<int,int> dp[MAXN][20];
bool li[MAXN][20];

pair<int,int> ff(int x,int p){
    if(x==0)return {n,0};
    if(p==0)return {parent[x],win[parent[x]]};

    if(li[x][p])return dp[x][p];
    li[x][p]=true;

    dp[x][p].first=ff(ff(x,p-1).first,p-1).first;
    dp[x][p].second=max( ff(x,p-1).second , ff(ff(x,p-1).first,p-1).second );
    
    return dp[x][p];
}

pair<int,long long> dp2[MAXN][20];
bool li2[MAXN][20];

pair<int,long long> ff2(int x,int p){
    if(p==0)return {to[x],lose[x]};

    if(li2[x][p])return dp2[x][p];
    li2[x][p]=true;

    dp2[x][p].first=ff2(ff2(x,p-1).first,p-1).first;
    dp2[x][p].second=ff2(x,p-1).second + ff2(ff2(x,p-1).first,p-1).second;
    
    return dp2[x][p];
}

void dfs(int x,long long len){
    len+=win[x]; dist[x]=len;
    for(int i=0;i<v[x].size();i++){
        dfs(v[x][i],len);
    }
}

bool in[MAXN],dali,incyc[MAXN];
vector< vector<int> > cycle;
vector< vector<long long> > prefsum;
long long sum[MAXN];
int u[MAXN],tim;

void init(int N,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
    n=N;
    for(int i=0;i<n;i++){
        parent[i]=w[i];
        v[parent[i]].push_back(i);

        to[i]=l[i];

        win[i]=s[i]; lose[i]=p[i];
    }
    parent[n]=n; to[n]=n;

    dfs(n,0);

    cycle.push_back({});

    for(int i=0;i<n;i++){
        if(u[i]!=0)continue;
        tim++; x=i;

        while(true){
            u[x]=tim; x=to[x];
            if(u[x]>0 and u[x]!=tim)break;

            if(u[x]==tim){
                last=x; k++; comp[x]=k; sum[k]=lose[x];
                cycle.push_back({x}); incyc[x]=true; x=to[x];
                if(k!=int(cycle.size())+1)cout<<1/0;
                while(x!=last){
                    cycle[k].push_back(x); comp[x]=k; 
                    sum[k]+=lose[x]; u[x]=tim; incyc[x]=true;
                    x=to[x];
                }
                break;
            }
        }
    }

    for(int i=0;i<=k;i++){
        reverse(cycle[i].begin(),cycle[i].end());
        for(int f=0;f<cycle[i].size();f++){
            pos[cycle[i][f]]=f;
        }
    }
}

long long simulate(int x, int z){
    curr=z;

    while(x!=n){
        while(curr<win[x] and !incyc[x]){
            curr+=lose[x]; x=to[x];
        }
        
        if(curr<win[x]){            
            minloops=100000000; pref=0;

            /*
            for(int i=pos[x];i<cycle[comp[x]].size();i++){
                minloops=min( minloops, int( ceil(1.0*(win[cycle[comp[x]][i]]-curr-pref)/sum[comp[x]]) )*1LL );
                pref+=lose[cycle[comp[x]][i]];
            }
            for(int i=0;i<pos[x];i++){
                minloops=min( minloops, int( ceil(1.0*(win[cycle[comp[x]][i]]-curr-pref)/sum[comp[x]]) )*1LL );
                pref+=lose[cycle[comp[x]][i]];
            }
            */

            minloops=(win[0]-curr)/sum[comp[x]]-2;

            if(minloops<0)minloops=0;
            curr+=minloops*sum[comp[x]];

            for(int i=19;i>=0;i--){
                if(curr+ff2(x,i).second<win[0]){
                    curr+=ff2(x,i).second;
                    x=ff2(x,i).first;
                }
            }

            while(curr<win[x]){
                curr+=lose[x]; x=to[x];
            }
        }

        last=x;
        for(int i=19;i>=0;i--){
            if(ff(x,i).first!=n and ff(x,i).second<=curr){
                x=ff(x,i).first;
            }
        }

        curr+=dist[last]-dist[parent[x]];
        x=parent[x];
    }

    return curr;
}

/*
int main(){
    init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
    cout<<simulate(0,1)<<"\n";
    cout<<simulate(2,3)<<"\n";
}
*/

Compilation message (stderr)

dungeons.cpp: In function 'void dfs(int, long long int)':
dungeons.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:84:50: warning: division by zero [-Wdiv-by-zero]
   84 |                 if(k!=int(cycle.size())+1)cout<<1/0;
      |                                                 ~^~
dungeons.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int f=0;f<cycle[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~~

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