oj.uz

Submission #135449

# Submission time Handle Problem Language Result Execution time Memory
135449 2019-07-24T05:49:38 Z Talant Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 33056 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[101][N];
int sum;

vector <pair<int,int> > g[N];
void djikstra(int v,int o) {
      for (int i = 1; i <= n * m; i ++) d[o][i] = inf;
      d[o][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[o][v]) continue;
            for (auto to : g[v]) {
                  if (d[o][v] + to.sc < d[o][to.fr]) {
                        d[o][to.fr] = d[o][v] + to.sc;
                        q.push(mk(-d[o][to.fr],to.fr));
                  }
            }
      }
}

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]));
            }
      }
      for (int i = 1; i <= m; i ++)
            djikstra(i,i);
}

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;
      }
      for (int i = 1; i <= m; i ++)
            djikstra(i,i);
}

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;
      }
      for (int i = 1; i <= m; i ++)
            djikstra(i,i);
}
int escape(int V1, int V2) {
      if (m == 1) return sum;
      return d[++V1][(n - 1) * m + V2 + 1];
}

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:63:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < g[cur].size(); i ++) {
                       ~~^~~~~~~~~~~~~~~
wombats.cpp:66: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:77: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 83 ms 27896 KB Output is correct
2 Correct 83 ms 27896 KB Output is correct
3 Correct 153 ms 29560 KB Output is correct
4 Correct 82 ms 27896 KB Output is correct
5 Correct 82 ms 27896 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 23 ms 23800 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 24 ms 23844 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 25 ms 24056 KB Output is correct
5 Correct 26 ms 24056 KB Output is correct
6 Correct 24 ms 24056 KB Output is correct
7 Correct 26 ms 24056 KB Output is correct
8 Correct 25 ms 24056 KB Output is correct
9 Correct 28 ms 24056 KB Output is correct
10 Correct 25 ms 24056 KB Output is correct
11 Correct 101 ms 25080 KB Output is correct
12 Correct 26 ms 24056 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15831 ms 29260 KB Output is correct
2 Execution timed out 20018 ms 29200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 32096 KB Output is correct
2 Correct 1269 ms 32096 KB Output is correct
3 Correct 493 ms 32088 KB Output is correct
4 Correct 531 ms 33056 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15840 ms 29192 KB Output is correct
2 Execution timed out 20026 ms 29304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16111 ms 29264 KB Output is correct
2 Execution timed out 20049 ms 29304 KB Time limit exceeded
3 Halted 0 ms 0 KB -