제출 #135449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135449		Talant	웜뱃 (IOI13_wombats)	C++17	39 / 100	20049 ms	33056 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[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];
}

컴파일 시 표준 에러 (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: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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24