oj.uz

답안 #585269

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585269 2022-06-28T13:35:00 Z Dan4Life 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 104044 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
const int INF = (int)1e9;
const int maxn = 1000010;
vector<pair<int,int>> adj[maxn];
int dis[maxn], ind[5002][202];
int h[5002][202], v[5002][202], dp[5002][202];
bool vis[maxn];
int n, m;

int pref(int i, int j, int k){
    if(j==k) return 0; int ans = 0;
    if(j>k) swap(j,k);
    for(int l = j; l < k; l++) ans+=h[i][l];
    return ans;
}

int dijkstra(int s, int d){
    for(int i = 0; i <= n*m; i++) dis[i]=INF, vis[i] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,s}); dis[s] = 0;
    while(!pq.empty()){
        int a = pq.top().se; pq.pop();
        if(vis[a]) continue; vis[a] = 1;
        for(auto u : adj[a]){
            int b = u.fi, w = u.se;
            if(dis[b]>dis[a]+w){
                dis[b] = dis[a]+w;
                pq.push({dis[b], b});
            }
        }
    }
    return dis[d];
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    int _ = 0; n = R, m = C;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            ind[i][j] = _++;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(j<m-1){
                int x = ind[i][j], y = ind[i][j+1];
                adj[x].pb({y, H[i][j]});
                adj[y].pb({x, H[i][j]});
                h[i][j] = H[i][j];
            }
            if(i<n-1){
                int x = ind[i][j], y = ind[i+1][j];
                adj[x].pb({y, V[i][j]});
                v[i][j] = V[i][j];
            }
        }
    }
}

void changeH(int P, int Q, int W) {
    h[P][Q]=W; return;
    int x = ind[P][Q], y = ind[P][Q+1];
    for(auto &u : adj[x])
        if(u.fi==y) u.se=W;
    for(auto &u : adj[y])
        if(u.fi==x) u.se=W;
}

void changeV(int P, int Q, int W) {
    int x = ind[P][Q], y = ind[P+1][Q];
    v[P][Q]=W; return;
    for(auto &u : adj[x]) if(u.fi==y) u.se=W;
    for(auto &u : adj[y]) if(u.fi==x) u.se=W;
}

int escape(int V1, int V2) {
    dp[0][V1] = 0;
    for(int x = V1-1; x>=0; x--) dp[0][x] = dp[0][x+1]+h[0][x];
    for(int x = V1+1; x<m; x++) dp[0][x] = dp[0][x-1]+h[0][x-1];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < m; j++){
            dp[i][j] = INF;
            for(int k = 0; k < m; k++)
                dp[i][j] = min(dp[i][j], dp[i-1][k]+pref(i,j,k)+v[i-1][k]);
        }
    }
    return dp[n-1][V2];
    //return dijkstra(ind[0][V1], ind[n-1][V2]);
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'int pref(int, int, int)':
wombats.cpp:17:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   17 |     if(j==k) return 0; int ans = 0;
      |     ^~
wombats.cpp:17:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   17 |     if(j==k) return 0; int ans = 0;
      |                        ^~~
wombats.cpp: In function 'int dijkstra(int, int)':
wombats.cpp:29:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |         if(vis[a]) continue; vis[a] = 1;
      |         ^~
wombats.cpp:29:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |         if(vis[a]) continue; vis[a] = 1;
      |                              ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 39720 KB Output is correct
2 Correct 34 ms 39744 KB Output is correct
3 Correct 8077 ms 41320 KB Output is correct
4 Correct 41 ms 39756 KB Output is correct
5 Correct 44 ms 39708 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 15 ms 23788 KB Output is correct
8 Correct 12 ms 23832 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23716 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 33 ms 23852 KB Output is correct
5 Correct 38 ms 23896 KB Output is correct
6 Correct 34 ms 23916 KB Output is correct
7 Correct 36 ms 23920 KB Output is correct
8 Correct 33 ms 23892 KB Output is correct
9 Correct 32 ms 23936 KB Output is correct
10 Correct 29 ms 23924 KB Output is correct
11 Correct 11023 ms 24924 KB Output is correct
12 Correct 33 ms 23936 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2321 ms 24748 KB Output is correct
2 Correct 2193 ms 24848 KB Output is correct
3 Correct 2239 ms 24752 KB Output is correct
4 Correct 2204 ms 24752 KB Output is correct
5 Correct 2226 ms 24752 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 12 ms 23784 KB Output is correct
9 Correct 2252 ms 24760 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 47736 KB Output is correct
2 Correct 81 ms 47732 KB Output is correct
3 Correct 69 ms 47728 KB Output is correct
4 Correct 5505 ms 48424 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2218 ms 24752 KB Output is correct
2 Correct 2212 ms 24748 KB Output is correct
3 Correct 2264 ms 24704 KB Output is correct
4 Correct 2235 ms 24756 KB Output is correct
5 Correct 2246 ms 24748 KB Output is correct
6 Correct 82 ms 47684 KB Output is correct
7 Correct 67 ms 47828 KB Output is correct
8 Correct 67 ms 47656 KB Output is correct
9 Correct 5124 ms 48528 KB Output is correct
10 Correct 32 ms 39636 KB Output is correct
11 Correct 47 ms 39736 KB Output is correct
12 Correct 7890 ms 42580 KB Output is correct
13 Correct 44 ms 39764 KB Output is correct
14 Correct 32 ms 39764 KB Output is correct
15 Correct 12 ms 23784 KB Output is correct
16 Correct 12 ms 23804 KB Output is correct
17 Correct 12 ms 23828 KB Output is correct
18 Correct 32 ms 23892 KB Output is correct
19 Correct 32 ms 23892 KB Output is correct
20 Correct 34 ms 23816 KB Output is correct
21 Correct 33 ms 23928 KB Output is correct
22 Correct 29 ms 23924 KB Output is correct
23 Correct 31 ms 23876 KB Output is correct
24 Correct 31 ms 23828 KB Output is correct
25 Correct 10554 ms 26320 KB Output is correct
26 Correct 34 ms 23872 KB Output is correct
27 Correct 2230 ms 24832 KB Output is correct
28 Execution timed out 20047 ms 74216 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2135 ms 24756 KB Output is correct
2 Correct 2102 ms 24752 KB Output is correct
3 Correct 2151 ms 24752 KB Output is correct
4 Correct 2153 ms 24764 KB Output is correct
5 Correct 2089 ms 24752 KB Output is correct
6 Correct 64 ms 47624 KB Output is correct
7 Correct 79 ms 47736 KB Output is correct
8 Correct 65 ms 47740 KB Output is correct
9 Correct 6051 ms 48564 KB Output is correct
10 Correct 31 ms 39652 KB Output is correct
11 Correct 30 ms 39756 KB Output is correct
12 Correct 7085 ms 42536 KB Output is correct
13 Correct 33 ms 39764 KB Output is correct
14 Correct 32 ms 39672 KB Output is correct
15 Execution timed out 20090 ms 104044 KB Time limit exceeded
16 Halted 0 ms 0 KB -