Submission #1211496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211496		ksu2009en	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	59 ms	36680 KiB

dungeons

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

#include "dungeons.h"

vector<ll> s, p, w, l;
ll n;
ll win[(ll)(5e4 + 7)], comp[(ll)(5e4 + 7)];

vector<ll> d[(ll)(5e4 + 7)], d2[(ll)(5e4 + 7)];

void find_comp(ll v, ll step){
    comp[v] = step;
    
    for(auto i: d[v]){
        if(!comp[i])
            find_comp(i, step);
    }
}

vector<ll> ord;
ll used[(ll)(5e4 + 7)], par[(ll)(5e4 + 7)], tot[(ll)(5e4 + 7)];
pair<ll, ll> t[(ll)(5e4 + 7)][22];
bool loop[(ll)(5e4 + 7)];

void find_loop(ll v, ll prev){
    used[v] = 1;
    par[v] = prev;
    
    for(auto i: d2[v]){
        if(used[i] == 1){
            ll cur = v;
            
            while(cur != -1 && cur != i){
                ord.push_back(cur);
                cur = par[cur];
            }
            
            ord.push_back(i);
        }
        else if(!used[i]){
            find_loop(i, v);
        }
    }
    
    used[v] = 2;
}

ll par_pos[(ll)(5e4 + 7)];
vector<ll> pref[(ll)(5e4 + 7)];
vector<ll> loops[(ll)(5e4 + 7)];

void build(ll v, ll par){
    t[v][0].first = par;
    
    if(par != 0)
       t[v][0].second = p[v];
    
    for(ll i = 1; i < 20; i++){
        t[v][i].first = t[t[v][i - 1].first][i - 1].first;
        t[v][i].second = t[v][i - 1].second + t[t[v][i - 1].first][i - 1].second;
    }
    
    for(auto i: d[v]){
        if(i != par && !loop[i])
            build(i, v);
    }
}

void init(int n0, std::vector<int> s0, std::vector<int> p0, std::vector<int> w0, std::vector<int> l0){
    n = n0;
    
    s.clear();
    p.clear();
    w.clear();
    l.clear();
    
    for(int i = 0; i <= n; i++){
        pref[i].clear();
        loops[i].clear();
        d[i].clear();
        d2[i].clear();
        
        for(int j = 0; j < 20; j++)
            t[i][j].first = t[i][j].second = 0;
        
        par_pos[i] = used[i] = par[i] = tot[i] = loop[i] = win[i] = comp[i] = 0;
    }
    
    s.resize(n + 1);
    p.resize(n + 1);
    w.resize(n + 1);
    l.resize(n + 1);
    
    for(ll i = 1; i <= n; i++){
        s[i] = s0[i - 1], p[i] = p0[i - 1], w[i] = w0[i - 1], l[i] = l0[i - 1];
        w[i]++, l[i]++;
    }
    
    for(ll i = n; i >= 1; i--)
        win[i] = win[w[i]] + (ll)s[i];
    
    for(ll i = 1; i <= n; i++){
        d[i].push_back(l[i]);
        d[l[i]].push_back(i);
    }
    
    ll step = 0;
    for(ll i = 1; i <= n; i++)
        if(!comp[i])
            find_comp(i, ++step);
    
    vector<ll> st(n + 1), in(n + 1);
    for(int i = 1; i <= n; i++)
        in[l[i]]++;
    
    for(int i = 1; i <= n; i++){
        if(st[comp[i]] == 0 || in[i] == 0)
            st[comp[i]] = i;
    }
    
    for(ll i = 1; i <= n; i++){
        d2[i].push_back(l[i]);
    }

    vector<bool> used_comp(step + 1);
    
    for(ll i = 1; i <= n; i++){
        if(used_comp[comp[i]])
            continue;
        
        used_comp[comp[i]] = true;
        
        ord.clear();
        find_loop(st[comp[i]], -1);
        reverse(ord.begin(), ord.end());
        
        loops[comp[i]] = ord;
        
        for(auto j: ord)
            loop[j] = true;
        
//        cout << i << ' ' << (ll)(ord.size()) << endl;
//        for(auto j: ord)
//            cout << j << ' ';
//        cout << endl;
        
        for(ll j = 0; j < (ll)(ord.size()); j++){
            build(ord[j], 0);
            par_pos[ord[j]] = j;
        }
                
        for(auto j: ord)
            tot[comp[i]] += p[j];
        
        pref[comp[i]].resize((ll)(ord.size()));
        for(ll j = 0; j < (ll)(ord.size()); j++)
            pref[comp[i]][j] = (j == 0 ? 0 : pref[comp[i]][j - 1]) + p[ord[j]];
        
        for(auto j: ord)
            loop[j] = false;
    }
}

ll get_sum(ll c, ll pos, ll mid){
    if(mid == 0 || pref[c].empty())
        return 0;
    
    ll cnt = 0;
    if(pos + mid - 1 < (ll)(pref[c].size())){
        cnt = pref[c][pos + mid - 1];
        if(pos != 0)
            cnt -= pref[c][pos - 1];
    }
    else{
        ll can = (ll)(pref[c].size()) - pos;
        
        cnt = pref[c].back();
        if(pos != 0)
            cnt -= pref[c][pos - 1];

        ll need = mid - can;
        cnt += pref[c][need - 1];
    }
    
    return cnt;
}

ll cor(ll x, ll z){
    while(x != n + 1){
        if(z >= s[x]){
            z += s[x];
            x = w[x];
        }
        else{
            z += p[x];
            x = l[x];
        }
    }
    
    return z;
}

long long simulate(int x, int z){
    x++;
        
    if(z >= s[1])
        return z + win[x];
        
    if(t[x][0].first != 0){
        if(t[x][19].second + z < s[1]){
            z += t[x][19].second;
            
            for(ll i = 19; i >= 0; i--)
                if(t[x][i].first != 0)
                    x = t[x][i].first;
        }
        else{
            for(ll i = 19; i >= 0; i--){
                if(z + t[x][i].second < s[1]){
                    z += t[x][i].second;
                    x = t[x][i].first;
                }
            }
            
            // one more step:
            
            z += t[x][0].second;
            x = t[x][0].first;
        }
    }
    
    if(z >= s[1])
        return z + win[x];
    
    ll full = tot[comp[x]];
    ll need = (s[1] - z) / full;
    z += full * need;
    
//    cout << z << ' ' << x << endl;
    
//    cout << tot[comp[x]] << ' ' << full << ' ' << need << endl;
    
    ll c = comp[x], pos = par_pos[x];
    
    ll l = 0, r = (ll)(pref[c].size());
    
    while(l < r){
        ll mid = (l + r) >> 1;
        
        ll cnt = get_sum(c, pos, mid);
        
        if(z + cnt >= s[1])
            r = mid;
        else
            l = mid + 1;
    }
    
//    cout << "LEN " << l << endl;
    z += get_sum(c, pos, l);
//    cout << pos << endl;
//    for(auto i: loops[c])
//        cout << i << ' ';
//    cout << endl;
//
//    cout << z << endl;
    
    if(!pref[c].empty()){
        
        pos = (pos + l) % (ll)(pref[c].size());
        x = loops[comp[x]][pos];
    }
        
    return z + win[x];
}

/*
 3 1
 5 5 5
 2 1 3
 2 2 3
 1 0 1
 2 17
 
 
 2 3
 
 */

/*
 4 10
 16 16 16 16
 7 1 3 2
 1 3 4 4
 1 0 0 2
 0 4
 0 1
 0 5
 3 4
 2 6
 2 1
 3 0
 3 1
 1 1
 1 4
 
 4 1
 16 16 16 16
 7 1 3 2
 1 3 4 4
 1 0 0 2
 0 1
 
 
 */

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