Submission #720887

#	Time	Username	Problem	Language	Result	Execution time	Memory
720887		urosk	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7096 ms	63680 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
#define maxn 400005
#define lg 20
ll n;
vector<ll> g[maxn];
vector<ll> v[maxn];
ll a[maxn],b[maxn];
bool sub3 = 1;
bool sub1 = 1;
ll dis[maxn];
ll deg[maxn];
ll st[maxn][lg];
ll sum[maxn][lg];
ll cyc[maxn];
ll val[maxn];
ll len[maxn];
bool vis[maxn];
ll tsz = 0;
void dfs(ll u,ll p){
    for(ll s : v[u]){
        if(s==p) continue;
        dis[s] = dis[u] + 1;
        dfs(s,u);
    }
}
void dfs2(ll u,ll p){
    vis[u] = 1;
    cyc[u] = tsz;
    val[tsz]+=b[u];
    len[tsz]++;
    for(ll s : g[u]){
        if(vis[s]) continue;
        dfs2(s,u);
    }
}
bool sub2 = 0;
void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	n = N;
	for(ll i = 1;i<=n;i++) a[i] = s[i-1];
	for(ll i = 1;i<=n;i++) b[i] = p[i-1];
	for(ll i = 1;i<n;i++) sub3&=(a[i]==a[i+1]);
    for(ll i = 1;i<=n;i++){
        if(sub3) v[w[i-1]+1].pb(i);
        else v[i].pb(w[i-1]+1);
    }
    for(ll i = 1;i<=n;i++) g[i].pb(l[i-1]+1);
    if(sub3){
        dfs(n+1,n+1);
        for(ll i = 1;i<=n;i++){
            for(ll j : g[i]) deg[j]++;
        }
        queue<ll> q;
        for(ll i = 1;i<=n+1;i++) if(!deg[i]) q.push(i);
        for(ll i = 1;i<=n;i++) cyc[i] = 1;
        while(q.size()){
            ll u = q.front();
            q.pop();
            cyc[u] = 0;
            for(ll s : g[u]){
                deg[s]--;
                if(!deg[s]) q.push(s);
            }
        }
        for(ll i = 1;i<=n;i++){
            st[i][0] = g[i][0];
            sum[i][0] = b[i];
        }
        st[n+1][0] = n+1;
        for(ll j = 1;j<lg;j++){
            for(ll i = 1;i<=n+1;i++){
                st[i][j] = st[st[i][j-1]][j-1];
                sum[i][j] = sum[i][j-1] + sum[st[i][j-1]][j-1];
            }
        }
        for(ll i = 1;i<=n;i++){
            if(!cyc[i]) continue;
            if(vis[i]) continue;
            ++tsz;
            dfs2(i,i);
        }
    }
	return;
}

long long simulate(int x, int z) {
    if(sub2) return 0;
    x++;
    if(!sub3){
        while(x!=n+1){
            if(z>=a[x]){
                z+=a[x];
                x = v[x][0];
            }else{
                z+=b[x];
                x = g[x][0];
            }
        }
        return z;
    }
    ll s = a[1];
    for(ll j = lg-1;j>=0;j--){
        if(cyc[st[x][j]]) continue;
        if(sum[x][j]+z<s) x = st[x][j],z+=sum[x][j];
    }
    if(x==n+1) return z;
    if(z+b[x]>=s){
        return z + b[x] + s*dis[g[x][0]];
    }
    z+=b[x];
    x = g[x][0];
    if(x==n+1) return z;
    z+=((s-z)/val[cyc[x]])*val[cyc[x]];
    if(z==s) return s + s*dis[x];
    for(ll j = lg-1;j>=0;j--){
        if(sum[x][j]>val[cyc[x]]) continue;
        if(z+sum[x][j]<s) x = st[x][j];
    }
    z+=b[x];
    x = g[x][0];
	return z + s*dis[x];
}
/**
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
**/

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