oj.uz

Submission #585220

# Submission time Handle Problem Language Result Execution time Memory
585220 2022-06-28T12:45:33 Z Dan4Life Wombats (IOI13_wombats) C++17
12 / 100
 20000 ms 35924 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];
bool vis[maxn];
int n, m;

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]});
            }
            if(i<n-1){
                int x = ind[i][j], y = ind[i+1][j];
                adj[x].pb({y, V[i][j]});
            }
        }
    }
}

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

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

int escape(int V1, int 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 dijkstra(int, int)':
wombats.cpp:21:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |         if(vis[a]) continue; vis[a] = 1;
      |         ^~
wombats.cpp:21:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |         if(vis[a]) continue; vis[a] = 1;
      |                              ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 31840 KB Output is correct
2 Correct 70 ms 31836 KB Output is correct
3 Execution timed out 20080 ms 34580 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 11 ms 23756 KB Output is correct
3 Correct 12 ms 23788 KB Output is correct
4 Correct 27 ms 23868 KB Output is correct
5 Correct 20 ms 23764 KB Output is correct
6 Correct 19 ms 23852 KB Output is correct
7 Correct 31 ms 23764 KB Output is correct
8 Correct 24 ms 23884 KB Output is correct
9 Correct 31 ms 23872 KB Output is correct
10 Correct 24 ms 23764 KB Output is correct
11 Correct 7049 ms 24840 KB Output is correct
12 Correct 33 ms 23864 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 24552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 407 ms 35924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 24556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 24556 KB Output isn't correct
2 Halted 0 ms 0 KB -