Submission #135434

#	Time	Username	Problem	Language	Result	Execution time	Memory
135434		Talant	Wombats (IOI13_wombats)	C++17	37 / 100	20092 ms	32672 KiB

wombats

#include "wombats.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

#define sc second
#define fr first
#define mk make_pair
#define pb push_back

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);

int n,m;
int d[N];
int sum;

vector <pair<int,int> > g[N];

void init(int R, int C, int H[5000][200], int V[5000][200]) {
      n = R,m = C;

      for (int i = 1; i <= n; i ++) {
            for (int j = 1; j < m; j ++) {
                  int cur = (i - 1) * m + j;
                  g[cur].pb(mk(cur + 1,H[i - 1][j - 1]));
                  g[cur + 1].pb(mk(cur,H[i - 1][j - 1]));
            }
      }
      for (int i = 1; i < n; i ++) {
            for (int j = 1; j <= m; j ++) {
                  int cur = (i - 1) * m + j;
                  sum += V[i - 1][j - 1];
                  g[cur].pb(mk(cur + m,V[i - 1][j - 1]));
            }
      }
}

void changeH(int P, int Q, int W) {
      P ++,Q ++;
      int cur = (P - 1) * m + Q;
      for (int i = 0; i < g[cur].size(); i ++) {
            if (g[cur][i].fr == cur + 1) g[cur][i].sc = W;
      }
      for (int i = 0; i < g[cur + 1].size(); i ++) {
            if (g[cur + 1][i].fr == cur) g[cur + 1][i].sc = W;
      }
}

void changeV(int P, int Q, int W) {
      P ++,Q ++;
      int cur = (P - 1) * m + Q;
      sum += W;
      for (int i = 0; i < g[cur].size(); i ++) {
            if (g[cur][i].fr == cur + m) sum -= g[cur][i].sc,g[cur][i].sc = W;
      }
}
void djikstra(int v) {
      for (int i = 1; i <= n * m; i ++) d[i] = inf;
      d[v] = 0;
      priority_queue<pair<int,int> > q;
      q.push(mk(0,v));

      while (!q.empty()) {
            int v = q.top().sc,cur = -q.top().fr;
            q.pop();
            if (cur > d[v]) continue;
            for (auto to : g[v]) {
                  if (d[v] + to.sc < d[to.fr]) {
                        d[to.fr] = d[v] + to.sc;
                        q.push(mk(-d[to.fr],to.fr));
                  }
            }
      }
}
int escape(int V1, int V2) {
      if (m == 1) return sum;
      V1 ++,V2 ++;


      djikstra(V1);
      return d[(n - 1) * m + 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]
  int res;
      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:43:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < g[cur].size(); i ++) {
                       ~~^~~~~~~~~~~~~~~
wombats.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < g[cur + 1].size(); i ++) {
                       ~~^~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:55:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < g[cur].size(); i ++) {
                       ~~^~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24