oj.uz

Submission #135434

# Submission time Handle Problem Language Result Execution time Memory
135434 2019-07-24T05:36:08 Z Talant Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 32672 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28028 KB Output is correct
2 Correct 28 ms 27896 KB Output is correct
3 Correct 98 ms 29816 KB Output is correct
4 Correct 27 ms 27896 KB Output is correct
5 Correct 28 ms 27896 KB Output is correct
6 Correct 29 ms 23800 KB Output is correct
7 Correct 23 ms 23772 KB Output is correct
8 Correct 23 ms 23864 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 44 ms 23928 KB Output is correct
5 Correct 33 ms 23928 KB Output is correct
6 Correct 35 ms 23928 KB Output is correct
7 Correct 73 ms 23928 KB Output is correct
8 Correct 45 ms 23928 KB Output is correct
9 Correct 42 ms 23928 KB Output is correct
10 Correct 40 ms 23928 KB Output is correct
11 Correct 8791 ms 25240 KB Output is correct
12 Correct 49 ms 23928 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 24696 KB Output is correct
2 Correct 258 ms 24744 KB Output is correct
3 Correct 180 ms 24568 KB Output is correct
4 Correct 179 ms 24696 KB Output is correct
5 Correct 183 ms 24568 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 256 ms 24696 KB Output is correct
10 Correct 30 ms 23800 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 32128 KB Output is correct
2 Correct 1251 ms 32120 KB Output is correct
3 Correct 483 ms 32248 KB Output is correct
4 Execution timed out 20028 ms 32672 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 24568 KB Output is correct
2 Correct 260 ms 24568 KB Output is correct
3 Correct 184 ms 24696 KB Output is correct
4 Correct 187 ms 24568 KB Output is correct
5 Correct 178 ms 24568 KB Output is correct
6 Correct 481 ms 32048 KB Output is correct
7 Correct 1279 ms 32120 KB Output is correct
8 Correct 488 ms 32120 KB Output is correct
9 Execution timed out 20024 ms 32584 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 24564 KB Output is correct
2 Correct 257 ms 24640 KB Output is correct
3 Correct 180 ms 24640 KB Output is correct
4 Correct 178 ms 24576 KB Output is correct
5 Correct 179 ms 24568 KB Output is correct
6 Correct 480 ms 32040 KB Output is correct
7 Correct 1265 ms 32176 KB Output is correct
8 Correct 484 ms 32252 KB Output is correct
9 Execution timed out 20092 ms 32600 KB Time limit exceeded
10 Halted 0 ms 0 KB -