oj.uz

Submission #135429

# Submission time Handle Problem Language Result Execution time Memory
135429 2019-07-24T05:29:09 Z Talant Wombats (IOI13_wombats) C++17
28 / 100
 20000 ms 33224 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];

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;
                  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;
      for (int i = 0; i < g[cur].size(); i ++) {
            if (g[cur][i].fr == cur + m) 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) {
      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:41:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < g[cur].size(); i ++) {
                       ~~^~~~~~~~~~~~~~~
wombats.cpp:44: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:52:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < g[cur].size(); i ++) {
                       ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 27896 KB Output is correct
2 Correct 82 ms 27900 KB Output is correct
3 Execution timed out 20049 ms 30836 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 22 ms 23800 KB Output is correct
4 Correct 43 ms 23928 KB Output is correct
5 Correct 33 ms 23928 KB Output is correct
6 Correct 34 ms 23928 KB Output is correct
7 Correct 50 ms 23980 KB Output is correct
8 Correct 44 ms 23932 KB Output is correct
9 Correct 41 ms 23900 KB Output is correct
10 Correct 40 ms 23932 KB Output is correct
11 Correct 8911 ms 25104 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 186 ms 24440 KB Output is correct
2 Correct 264 ms 24716 KB Output is correct
3 Correct 183 ms 24696 KB Output is correct
4 Correct 182 ms 24660 KB Output is correct
5 Correct 185 ms 24640 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23800 KB Output is correct
9 Correct 261 ms 24700 KB Output is correct
10 Correct 24 ms 23800 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 32164 KB Output is correct
2 Correct 1261 ms 32232 KB Output is correct
3 Correct 481 ms 32104 KB Output is correct
4 Execution timed out 20067 ms 33196 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 24568 KB Output is correct
2 Correct 274 ms 24716 KB Output is correct
3 Correct 182 ms 24568 KB Output is correct
4 Correct 183 ms 24824 KB Output is correct
5 Correct 185 ms 24696 KB Output is correct
6 Correct 482 ms 32124 KB Output is correct
7 Correct 1256 ms 32348 KB Output is correct
8 Correct 487 ms 32248 KB Output is correct
9 Execution timed out 20083 ms 33224 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 24640 KB Output is correct
2 Correct 286 ms 24720 KB Output is correct
3 Correct 189 ms 24696 KB Output is correct
4 Correct 244 ms 24660 KB Output is correct
5 Correct 184 ms 24720 KB Output is correct
6 Correct 524 ms 31992 KB Output is correct
7 Correct 1264 ms 32120 KB Output is correct
8 Correct 496 ms 32220 KB Output is correct
9 Execution timed out 20098 ms 33176 KB Time limit exceeded
10 Halted 0 ms 0 KB -