oj.uz

답안 #442402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442402 2021-07-07T17:14:28 Z Pajaraja 던전 (IOI21_dungeons) C++17
100 / 100
 4536 ms 1658404 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define MAXN 400007
#define MAXL 25
#define MAXK 8
using namespace std;
vector<int> s,p,w,l,g[MAXN],we[MAXN];
long long sum[MAXK][MAXL][MAXN],mn[MAXK][MAXL][MAXN],add[MAXN],stp[10];
int pr[MAXK][MAXL][MAXN],n;
void dfs(int s,long long a)
{
    add[s]=a;
    for(int i=0;i<g[s].size();i++) dfs(g[s][i],a+we[s][i]);
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n=N; s=S; p=P; w=W; l=L; w.push_back(n); l.push_back(n); s.push_back(0); p.push_back(0);
	stp[0]=1; for(int i=1;i<10;i++) stp[i]=stp[i-1]*8;
	for(int k=0;k<MAXK;k++)
    {
        int st=stp[k];
        for(int i=0;i<n;i++)
        {
            if(s[i]<=st) {pr[k][0][i]=w[i]; sum[k][0][i]=s[i]; mn[k][0][i]=1000000000000000000LL;}
            else {pr[k][0][i]=l[i]; sum[k][0][i]=p[i]; mn[k][0][i]=s[i];}
        }
        pr[k][0][n]=n; sum[k][0][n]=0; mn[k][0][n]=1000000000000000000LL;
        for(int j=1;j<MAXL;j++) for(int i=0;i<=n;i++)
        {
            pr[k][j][i]=pr[k][j-1][pr[k][j-1][i]];
            sum[k][j][i]=sum[k][j-1][i]+sum[k][j-1][pr[k][j-1][i]]; if(sum[k][j][i]>1000000000000000000LL) sum[k][j][i]=1000000000000000000LL;
            mn[k][j][i]=min(mn[k][j-1][i],mn[k][j-1][pr[k][j-1][i]]-sum[k][j-1][i]);
        }
    }
    for(int i=0;i<n;i++) {g[w[i]].push_back(i); we[w[i]].push_back(s[i]);}
    dfs(n,0);
}

long long simulate(int x, int z) {
    long long st=z;
    for(int k=0;k<MAXK;k++)
    {
        while(true)
        {
            if(st>=stp[k+1] || x==n) break;
            for(int j=MAXL-1;j>=0;j--) if(mn[k][j][x]>st) {st+=sum[k][j][x]; x=pr[k][j][x];}
            st+=s[x]; x=w[x];
        }
    }
	return st+add[x];
}

Compilation message

dungeons.cpp: In function 'void dfs(int, long long int)':
dungeons.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<g[s].size();i++) dfs(g[s][i],a+we[s][i]);
      |                 ~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23628 KB Output is correct
2 Correct 15 ms 23628 KB Output is correct
3 Correct 21 ms 31652 KB Output is correct
4 Correct 189 ms 223796 KB Output is correct
5 Correct 22 ms 31632 KB Output is correct
6 Correct 196 ms 224524 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 27724 KB Output is correct
2 Correct 1379 ms 1638640 KB Output is correct
3 Correct 1316 ms 1657520 KB Output is correct
4 Correct 1341 ms 1658404 KB Output is correct
5 Correct 1623 ms 1627988 KB Output is correct
6 Correct 1501 ms 1645420 KB Output is correct
7 Correct 1464 ms 1656188 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 27676 KB Output is correct
2 Correct 290 ms 224840 KB Output is correct
3 Correct 245 ms 227116 KB Output is correct
4 Correct 239 ms 228640 KB Output is correct
5 Correct 202 ms 227036 KB Output is correct
6 Correct 332 ms 224864 KB Output is correct
7 Correct 307 ms 224820 KB Output is correct
8 Correct 217 ms 228572 KB Output is correct
9 Correct 241 ms 224624 KB Output is correct
10 Correct 222 ms 228516 KB Output is correct
11 Correct 229 ms 225280 KB Output is correct
12 Correct 340 ms 225460 KB Output is correct
13 Correct 273 ms 223744 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 27676 KB Output is correct
2 Correct 290 ms 224840 KB Output is correct
3 Correct 245 ms 227116 KB Output is correct
4 Correct 239 ms 228640 KB Output is correct
5 Correct 202 ms 227036 KB Output is correct
6 Correct 332 ms 224864 KB Output is correct
7 Correct 307 ms 224820 KB Output is correct
8 Correct 217 ms 228572 KB Output is correct
9 Correct 241 ms 224624 KB Output is correct
10 Correct 222 ms 228516 KB Output is correct
11 Correct 229 ms 225280 KB Output is correct
12 Correct 340 ms 225460 KB Output is correct
13 Correct 273 ms 223744 KB Output is correct
14 Correct 20 ms 27672 KB Output is correct
15 Correct 239 ms 224900 KB Output is correct
16 Correct 291 ms 224680 KB Output is correct
17 Correct 206 ms 226176 KB Output is correct
18 Correct 221 ms 227128 KB Output is correct
19 Correct 327 ms 225520 KB Output is correct
20 Correct 271 ms 227636 KB Output is correct
21 Correct 273 ms 227692 KB Output is correct
22 Correct 251 ms 226988 KB Output is correct
23 Correct 247 ms 225924 KB Output is correct
24 Correct 421 ms 225716 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 27676 KB Output is correct
2 Correct 290 ms 224840 KB Output is correct
3 Correct 245 ms 227116 KB Output is correct
4 Correct 239 ms 228640 KB Output is correct
5 Correct 202 ms 227036 KB Output is correct
6 Correct 332 ms 224864 KB Output is correct
7 Correct 307 ms 224820 KB Output is correct
8 Correct 217 ms 228572 KB Output is correct
9 Correct 241 ms 224624 KB Output is correct
10 Correct 222 ms 228516 KB Output is correct
11 Correct 229 ms 225280 KB Output is correct
12 Correct 340 ms 225460 KB Output is correct
13 Correct 273 ms 223744 KB Output is correct
14 Correct 20 ms 27672 KB Output is correct
15 Correct 239 ms 224900 KB Output is correct
16 Correct 291 ms 224680 KB Output is correct
17 Correct 206 ms 226176 KB Output is correct
18 Correct 221 ms 227128 KB Output is correct
19 Correct 327 ms 225520 KB Output is correct
20 Correct 271 ms 227636 KB Output is correct
21 Correct 273 ms 227692 KB Output is correct
22 Correct 251 ms 226988 KB Output is correct
23 Correct 247 ms 225924 KB Output is correct
24 Correct 421 ms 225716 KB Output is correct
25 Correct 196 ms 224488 KB Output is correct
26 Correct 278 ms 226248 KB Output is correct
27 Correct 238 ms 225572 KB Output is correct
28 Correct 271 ms 225548 KB Output is correct
29 Correct 289 ms 225940 KB Output is correct
30 Correct 294 ms 229516 KB Output is correct
31 Correct 315 ms 229272 KB Output is correct
32 Correct 479 ms 226056 KB Output is correct
33 Correct 959 ms 227124 KB Output is correct
34 Correct 1578 ms 227076 KB Output is correct
35 Correct 827 ms 226068 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 27724 KB Output is correct
2 Correct 1379 ms 1638640 KB Output is correct
3 Correct 1316 ms 1657520 KB Output is correct
4 Correct 1341 ms 1658404 KB Output is correct
5 Correct 1623 ms 1627988 KB Output is correct
6 Correct 1501 ms 1645420 KB Output is correct
7 Correct 1464 ms 1656188 KB Output is correct
8 Correct 19 ms 27676 KB Output is correct
9 Correct 290 ms 224840 KB Output is correct
10 Correct 245 ms 227116 KB Output is correct
11 Correct 239 ms 228640 KB Output is correct
12 Correct 202 ms 227036 KB Output is correct
13 Correct 332 ms 224864 KB Output is correct
14 Correct 307 ms 224820 KB Output is correct
15 Correct 217 ms 228572 KB Output is correct
16 Correct 241 ms 224624 KB Output is correct
17 Correct 222 ms 228516 KB Output is correct
18 Correct 229 ms 225280 KB Output is correct
19 Correct 340 ms 225460 KB Output is correct
20 Correct 273 ms 223744 KB Output is correct
21 Correct 20 ms 27672 KB Output is correct
22 Correct 239 ms 224900 KB Output is correct
23 Correct 291 ms 224680 KB Output is correct
24 Correct 206 ms 226176 KB Output is correct
25 Correct 221 ms 227128 KB Output is correct
26 Correct 327 ms 225520 KB Output is correct
27 Correct 271 ms 227636 KB Output is correct
28 Correct 273 ms 227692 KB Output is correct
29 Correct 251 ms 226988 KB Output is correct
30 Correct 247 ms 225924 KB Output is correct
31 Correct 421 ms 225716 KB Output is correct
32 Correct 196 ms 224488 KB Output is correct
33 Correct 278 ms 226248 KB Output is correct
34 Correct 238 ms 225572 KB Output is correct
35 Correct 271 ms 225548 KB Output is correct
36 Correct 289 ms 225940 KB Output is correct
37 Correct 294 ms 229516 KB Output is correct
38 Correct 315 ms 229272 KB Output is correct
39 Correct 479 ms 226056 KB Output is correct
40 Correct 959 ms 227124 KB Output is correct
41 Correct 1578 ms 227076 KB Output is correct
42 Correct 827 ms 226068 KB Output is correct
43 Correct 15 ms 23700 KB Output is correct
44 Correct 19 ms 27776 KB Output is correct
45 Correct 2237 ms 1630744 KB Output is correct
46 Correct 1678 ms 1627800 KB Output is correct
47 Correct 1668 ms 1628116 KB Output is correct
48 Correct 1417 ms 1648280 KB Output is correct
49 Correct 2424 ms 1630736 KB Output is correct
50 Correct 1432 ms 1647936 KB Output is correct
51 Correct 1363 ms 1643964 KB Output is correct
52 Correct 1460 ms 1645868 KB Output is correct
53 Correct 3413 ms 1632168 KB Output is correct
54 Correct 2511 ms 1642176 KB Output is correct
55 Correct 2984 ms 1641340 KB Output is correct
56 Correct 3407 ms 1632976 KB Output is correct
57 Correct 4536 ms 1633032 KB Output is correct
58 Correct 3777 ms 1633140 KB Output is correct
59 Correct 3894 ms 1633188 KB Output is correct
60 Correct 2867 ms 1639728 KB Output is correct
61 Correct 2592 ms 1640792 KB Output is correct