Submission #603983

#	Time	Username	Problem	Language	Result	Execution time	Memory
603983		keta_tsimakuridze	Dungeons Game (IOI21_dungeons)	C++17	62 / 100	7045 ms	1392072 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
#define pii pair<long long, long long>
#define f first
#define s second
using namespace std;
#include <vector>
vector<int> s, p, w, l;
int n;
const long long inf = 1e18;
const int N =4e5 + 5;
long long nxt[N][33][6], add[N][33][6], d[N][2], F, mx[N][33];
vector<int> val;
vector<pii> V[N][2];
void bfs(int t) {
    for(int i = 0; i < n; i++) d[i][t] = inf;
    queue<int> q;
    q.push(n);
    while(q.size()) {
        int u = q.front();
        q.pop();
        for(int i = 0; i < V[u][t].size(); i++) {
            d[V[u][t][i].f][t] = d[u][t] + V[u][t][i].s;
            q.push(V[u][t][i].f);
        }
    }
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    s = S; p = P; w = W; l = L;
    n = N;
    F = 1;
    for(int i = 0; i < n; i++) F &= (s[i] == p[i]);
    for(int i = 0; i < n; i++) {
        val.push_back(s[i]);
    }
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    if(val.size() <= 5 && n <= 50000) {
    for(int i = 0; i < n; i++) nxt[i][0][0] = l[i], add[i][0][0] = p[i];
    nxt[n][0][0] = nxt[n][0][1] = n;
    mx[n][0] = -inf;
    for(int i = 0; i < val.size(); i++) {
        nxt[n][0][i + 1] = n;
        for(int j = 0; j < n; j++) {
            if(s[j] <= val[i]) {
                nxt[j][0][i + 1] = w[j];
                add[j][0][i + 1] = s[j];
            } else nxt[j][0][i + 1] = l[j], add[j][0][i + 1] = p[j];
        }
    }
    for(int i = 1; i <= 30; i++) {
        for(int j = 0; j <= n; j++) {
            for(int t = 0; t <= val.size(); t++)
            nxt[j][i][t] = nxt[nxt[j][i - 1][t]][i - 1][t],
            add[j][i][t] = add[j][i -  1][t] + add[nxt[j][i - 1][t]][i - 1][t];
            int t = 1;
            mx[j][i] = max(mx[j][i - 1], -add[j][i - 1][t] + mx[nxt[j][i - 1][t]][i - 1]);
        }
    }
    for(int i = 0; i < n; i++) {
        V[w[i]][0].push_back({i, s[i]});
    }
    bfs(0);}
    else {
        mx[n][0] = -1e9;
    for(int i = 0; i < n; i++) nxt[i][0][1] = w[i], add[i][0][1] = s[i], mx[i][0] = s[i];
    nxt[n][0][0] = nxt[n][0][1] = n;
        for(int i = 1; i <= 30; i++) {
            for(int j = 0; j <= n; j++) {
                for(int t = 0; t < 2; t++)
                nxt[j][i][t] = nxt[nxt[j][i - 1][t]][i - 1][t],
                add[j][i][t] = add[j][i -  1][t] + add[nxt[j][i - 1][t]][i - 1][t];
                int t = 1;
                mx[j][i] = max(mx[j][i - 1], -add[j][i - 1][t] + mx[nxt[j][i - 1][t]][i - 1]);
            }
        }
    }
}
long long get2(int x, int Z) {
	long long  ans2 = Z;
	while(x != n) {
      //  cout << x << endl; system("pause");
        for(int i = 30; i >= 0; i--) {
            if(mx[x][i] <= ans2) {
                ans2 += add[x][i][1];
                x = nxt[x][i][1];
            } //else cout << "+" << 30 << endl;
        }
        if(x == n) break;
        ans2 += s[x];
        x = l[x];
	}
    return ans2;
}
long long get3(int x,int Z) {
    long long  ans2 = Z;
	for(int k = 0; k < val.size(); k++) {
        for(int i = 30; i >= 0; i--) {
            if(add[x][i][k] + ans2 < val[k]) {
                ans2 += add[x][i][k];
                x = nxt[x][i][k];
            }
        }
        if(ans2 < val[k]) {
            ans2 += add[x][0][k];
            x = nxt[x][0][k];
        }
	}
	return ans2 + d[x][0];
}
long long simulate(int x, int Z) {
    if(val.size() <= 5 && n <= 50000) return get3(x, Z);
    if(F) return get2(x, Z);
	long long z = Z;
	while(x != n) {
        if(z < s[x]) {
            z += p[x];
            x = l[x];
        } else z += s[x], x = w[x];
	}
    return z;
}

Compilation message (stderr)

dungeons.cpp: In function 'void bfs(int)':
dungeons.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i = 0; i < V[u][t].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < val.size(); i++) {
      |                    ~~^~~~~~~~~~~~
dungeons.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int t = 0; t <= val.size(); t++)
      |                            ~~^~~~~~~~~~~~~
dungeons.cpp: In function 'long long int get3(int, int)':
dungeons.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int k = 0; k < val.size(); k++) {
      |                 ~~^~~~~~~~~~~~

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