Submission #550903

#	Time	Username	Problem	Language	Result	Execution time	Memory
550903		topovik	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	2980 ms	2097152 KiB

dungeons

#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pi acos(-1)

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e18;
const ld eps = (ld)1 / oo;
const ll N = 2e5 + 100;
const ll MX = 500;
const ll M = 30;

vector <vector <vector <pair<int, ll> > > > binpow;
vector <ll> str;
vector <int> s, p, w, l;
int n;

int mx = 0;

void init(int n1, vector <int> s1, vector <int> p1, vector <int> w1, vector <int> l1)
{
    n = n1;
    s = s1, p = p1, w = w1, l = l1;
    for (ll i = 0; i < n; i++) str.pb(s[i]);
    str.pb(0);
    sort(str.begin(), str.end());
    str.resize(unique(str.begin(), str.end()) - str.begin());
    str.resize(min((int)MX, (int)str.size()));
    binpow.resize(str.size());
    for (ll i = 0; i < str.size(); i++)
    {
        binpow[i].resize(n + 1);
        for (ll j = 0; j <= n; j++) binpow[i][j].resize(M);
        for (ll j = 0; j < n; j++)
          if (s[j] > str[i]) binpow[i][j][0] = {l[j], p[j]};
          else               binpow[i][j][0] = {w[j], s[j]};
        binpow[i][n][0] = {n, 0};
        for (ll c = 1; c < M; c++)
        {
            for (ll j = 0; j <= n; j++)
            {
                ll nx = binpow[i][j][c - 1].f;
                binpow[i][j][c].f = binpow[i][nx][c - 1].f;
                binpow[i][j][c].s = binpow[i][j][c - 1].s + binpow[i][nx][c - 1].s;
            }
        }
    }
}

ll simulate(int x, int y1)
{
    ll y = y1;
    for (int i = 0; i < str.size(); i++)
    {
        if (y < str[i])
        {
            for (int j = M - 1; j >= 0; j--)
                if (y + binpow[i - 1][x][j].s < str[i]) y += binpow[i - 1][x][j].s, x = binpow[i - 1][x][j].f;
            y += binpow[i - 1][x][0].s;
            x = binpow[i - 1][x][0].f;
            if (x == n) return y;
        }
    }
    while (x != n)
    {
        if (s[x] > y)
        {
            y += p[x];
            x = l[x];
        }
        else
        {
            y += s[x];
            x = w[x];
        }
    }
    return y;
}

//int main()
//{
//    srand(time(NULL));
//    ll n, q;
//    cin >> n >> q;
//    vector <int> a(n), b(n), c(n), d(n);
//    for (ll i = 0; i < n; i++) cin >> a[i];
//    for (ll i = 0; i < n; i++) cin >> b[i];
//    for (ll i = 0; i < n; i++) cin >> c[i];
//    for (ll i = 0; i < n; i++) cin >> d[i];
//    init(n, a, b, c, d);
//    while (q--)
//    {
//        ll x, z;
//        cin >> x >> z;
//        cout << simulate(x, z) << endl;
//    }
//}
/*
1
4
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
-100000 -100000 100000 -100000 -100000 100000
*/

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:36:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (ll i = 0; i < str.size(); i++)
      |                    ~~^~~~~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < str.size(); i++)
      |                     ~~^~~~~~~~~~~~

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