oj.uz

Submission #603983

# Submission time Handle Problem Language Result Execution time Memory
603983 2022-07-24T14:29:04 Z keta_tsimakuridze Dungeons Game (IOI21_dungeons) C++17
62 / 100
 7000 ms 1392072 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 11 ms 19156 KB Output is correct
3 Correct 17 ms 25940 KB Output is correct
4 Correct 150 ms 189736 KB Output is correct
5 Correct 14 ms 25956 KB Output is correct
6 Correct 139 ms 189616 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22508 KB Output is correct
2 Correct 1287 ms 1383552 KB Output is correct
3 Correct 1131 ms 1390648 KB Output is correct
4 Correct 1114 ms 1392072 KB Output is correct
5 Correct 1171 ms 1392060 KB Output is correct
6 Correct 1167 ms 1390580 KB Output is correct
7 Correct 1130 ms 1388860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22612 KB Output is correct
2 Correct 213 ms 192840 KB Output is correct
3 Correct 201 ms 192768 KB Output is correct
4 Correct 188 ms 192912 KB Output is correct
5 Correct 197 ms 192696 KB Output is correct
6 Correct 197 ms 192720 KB Output is correct
7 Correct 217 ms 192736 KB Output is correct
8 Correct 215 ms 193028 KB Output is correct
9 Correct 201 ms 192592 KB Output is correct
10 Correct 192 ms 192912 KB Output is correct
11 Correct 210 ms 192904 KB Output is correct
12 Correct 306 ms 192684 KB Output is correct
13 Correct 280 ms 192216 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22612 KB Output is correct
2 Correct 213 ms 192840 KB Output is correct
3 Correct 201 ms 192768 KB Output is correct
4 Correct 188 ms 192912 KB Output is correct
5 Correct 197 ms 192696 KB Output is correct
6 Correct 197 ms 192720 KB Output is correct
7 Correct 217 ms 192736 KB Output is correct
8 Correct 215 ms 193028 KB Output is correct
9 Correct 201 ms 192592 KB Output is correct
10 Correct 192 ms 192912 KB Output is correct
11 Correct 210 ms 192904 KB Output is correct
12 Correct 306 ms 192684 KB Output is correct
13 Correct 280 ms 192216 KB Output is correct
14 Correct 13 ms 22484 KB Output is correct
15 Correct 291 ms 192436 KB Output is correct
16 Correct 333 ms 192444 KB Output is correct
17 Correct 325 ms 192456 KB Output is correct
18 Correct 388 ms 192476 KB Output is correct
19 Correct 387 ms 192660 KB Output is correct
20 Correct 315 ms 192416 KB Output is correct
21 Correct 340 ms 192520 KB Output is correct
22 Correct 280 ms 192400 KB Output is correct
23 Correct 351 ms 192600 KB Output is correct
24 Correct 441 ms 192492 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22612 KB Output is correct
2 Correct 213 ms 192840 KB Output is correct
3 Correct 201 ms 192768 KB Output is correct
4 Correct 188 ms 192912 KB Output is correct
5 Correct 197 ms 192696 KB Output is correct
6 Correct 197 ms 192720 KB Output is correct
7 Correct 217 ms 192736 KB Output is correct
8 Correct 215 ms 193028 KB Output is correct
9 Correct 201 ms 192592 KB Output is correct
10 Correct 192 ms 192912 KB Output is correct
11 Correct 210 ms 192904 KB Output is correct
12 Correct 306 ms 192684 KB Output is correct
13 Correct 280 ms 192216 KB Output is correct
14 Correct 13 ms 22484 KB Output is correct
15 Correct 291 ms 192436 KB Output is correct
16 Correct 333 ms 192444 KB Output is correct
17 Correct 325 ms 192456 KB Output is correct
18 Correct 388 ms 192476 KB Output is correct
19 Correct 387 ms 192660 KB Output is correct
20 Correct 315 ms 192416 KB Output is correct
21 Correct 340 ms 192520 KB Output is correct
22 Correct 280 ms 192400 KB Output is correct
23 Correct 351 ms 192600 KB Output is correct
24 Correct 441 ms 192492 KB Output is correct
25 Correct 153 ms 189668 KB Output is correct
26 Correct 169 ms 190664 KB Output is correct
27 Correct 168 ms 190664 KB Output is correct
28 Correct 443 ms 190760 KB Output is correct
29 Correct 179 ms 190660 KB Output is correct
30 Execution timed out 7045 ms 190904 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22508 KB Output is correct
2 Correct 1287 ms 1383552 KB Output is correct
3 Correct 1131 ms 1390648 KB Output is correct
4 Correct 1114 ms 1392072 KB Output is correct
5 Correct 1171 ms 1392060 KB Output is correct
6 Correct 1167 ms 1390580 KB Output is correct
7 Correct 1130 ms 1388860 KB Output is correct
8 Correct 13 ms 22612 KB Output is correct
9 Correct 213 ms 192840 KB Output is correct
10 Correct 201 ms 192768 KB Output is correct
11 Correct 188 ms 192912 KB Output is correct
12 Correct 197 ms 192696 KB Output is correct
13 Correct 197 ms 192720 KB Output is correct
14 Correct 217 ms 192736 KB Output is correct
15 Correct 215 ms 193028 KB Output is correct
16 Correct 201 ms 192592 KB Output is correct
17 Correct 192 ms 192912 KB Output is correct
18 Correct 210 ms 192904 KB Output is correct
19 Correct 306 ms 192684 KB Output is correct
20 Correct 280 ms 192216 KB Output is correct
21 Correct 13 ms 22484 KB Output is correct
22 Correct 291 ms 192436 KB Output is correct
23 Correct 333 ms 192444 KB Output is correct
24 Correct 325 ms 192456 KB Output is correct
25 Correct 388 ms 192476 KB Output is correct
26 Correct 387 ms 192660 KB Output is correct
27 Correct 315 ms 192416 KB Output is correct
28 Correct 340 ms 192520 KB Output is correct
29 Correct 280 ms 192400 KB Output is correct
30 Correct 351 ms 192600 KB Output is correct
31 Correct 441 ms 192492 KB Output is correct
32 Correct 153 ms 189668 KB Output is correct
33 Correct 169 ms 190664 KB Output is correct
34 Correct 168 ms 190664 KB Output is correct
35 Correct 443 ms 190760 KB Output is correct
36 Correct 179 ms 190660 KB Output is correct
37 Execution timed out 7045 ms 190904 KB Time limit exceeded
38 Halted 0 ms 0 KB -