Submission #585220

#	Time	Username	Problem	Language	Result	Execution time	Memory
585220		Dan4Life	Wombats (IOI13_wombats)	C++17	12 / 100	20080 ms	35924 KiB

wombats

#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 (stderr)

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24