oj.uz

답안 #1074160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074160 2024-08-25T08:28:56 Z pravcoder 웜뱃 (IOI13_wombats) C++17
39 / 100
 294 ms 10824 KB 
#include "wombats.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef pair<int, int> pi;
typedef pair<int, pi> p2i;
typedef priority_queue<p2i> djpq; // priority queue for djikstras
typedef vector<bool> vb;
typedef vector<vb> v2b;

#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)

//sub1

v2i h, v;
int r, c;
int totw = 0;
bool sub1 = true;
bool sub2 = true;
bool sub3 = false;
bool sub4 = true;
v2i mindists;
v2b processed;
djpq q;
v3i s3dp; //sub 3 dp

void s3update(int r) {
    int s, c;
    if (r != 0) {
        rep(s, 2) {
            rep(c, 2) {
                s3dp[r][c][s] = min(s3dp[r - 1][c][s] + v[r - 1][c], s3dp[r - 1][1 - c][s] + v[r - 1][1 - c] + h[r][0]);
            }
        }
    }
    else {
        rep(s, 2) {
            s3dp[0][1-s][s] = h[0][0];
        }
    }
}

void sub2calc(int start) {
    //cout << "----------------------------Calculating minimum distances for " << start << "----------------------------\n";
    q.push({ 0, {0, start} });
    int d;
    while (!q.empty()) {
        p2i node = q.top();
        d = 0 - node.first;
        //cout << "Processing node (" << node.second.first << ", " << node.second.second << ") with distance " << d << "\n";
        q.pop();
        if (!processed[node.second.first][node.second.second]) {
            //cout << "Adding children\n";
            // process children of node
            if (node.second.second < c - 1) { // right 
                //cout << "Added right node ";
                int newdist = (d + h[node.second.first][node.second.second]);
                q.push({ 0 - newdist, {node.second.first, node.second.second + 1} });
                //cout << "with distance " << newdist << "\n";
            }
            if (node.second.second > 0) { // left
                //cout << "Added left node ";
                int newdist = (d + h[node.second.first][node.second.second - 1]);
                q.push({ 0 - newdist, {node.second.first, node.second.second - 1} });
                //cout << "with distance " << newdist << "\n";
            }
            if (node.second.first < r - 1) { // bottom
                //cout << "Added bottom node ";
                int newdist = (d + v[node.second.first][node.second.second]);
                q.push({ 0 - newdist, {node.second.first + 1, node.second.second} });
                //cout << "with distance " << newdist << "\n";
            }
            else {
                mindists[start][node.second.second] = d;
                //cout << "Minimum distance for " << node.second.second << " is " << d << "\n";
            }
            processed[node.second.first][node.second.second] = true;
        }
    }
}

int mindist4(int start, int end) {
    djpq q;
    //cout << "----------------------------Calculating minimum distances for " << start << "----------------------------\n";
    q.push({ 0, {0, start} });
    int d;
    while (!q.empty()) {
        p2i node = q.top();
        d = 0 - node.first;
        //cout << "Processing node (" << node.second.first << ", " << node.second.second << ") with distance " << d << "\n";
        q.pop();
        if (!processed[node.second.first][node.second.second]) {
            //cout << "Adding children\n";
            // process children of node
            if (node.second.second < c - 1) { // right 
                //cout << "Added right node ";
                int newdist = (d + h[node.second.first][node.second.second]);
                q.push({ 0 - newdist, {node.second.first, node.second.second + 1} });
                //cout << "with distance " << newdist << "\n";
            }
            if (node.second.second > 0) { // left
                //cout << "Added left node ";
                int newdist = (d + h[node.second.first][node.second.second - 1]);
                q.push({ 0 - newdist, {node.second.first, node.second.second - 1} });
                //cout << "with distance " << newdist << "\n";
            }
            if (node.second.first < r - 1) { // bottom
                //cout << "Added bottom node ";
                int newdist = (d + v[node.second.first][node.second.second]);
                q.push({ 0 - newdist, {node.second.first + 1, node.second.second} });
                //cout << "with distance " << newdist << "\n";
            }
            else {
                if (node.second.second == end) {
                    return d;
                }
                //cout << "Minimum distance for " << node.second.second << " is " << d << "\n";
            }
            processed[node.second.first][node.second.second] = true;
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    vi tmp;
    r = R, c = C;
    if (C != 1) sub1 = false;
    /*if (max(R, C) > 100) {
        sub2 = false;
    }*/
    if (C == 2) {
        sub3 = true;
        sub2 = false;
    }
    if (sub2) {
        mindists.resize(C, vi(C, 1000000000));
    } 

    //------debug------
    //sub1 = false, sub2 = false, sub3 = false;
    //-----------------
    rep(i, R) {
        tmp.clear();
        rep(j, C - 1) {
            tmp.pb(H[i][j]);
        }
        h.pb(tmp);
    }
    rep(i, R-1) {
        tmp.clear();
        rep(j, C) {
            tmp.pb(V[i][j]);
            if (sub1) totw += V[i][j];
        }
        v.pb(tmp);
    }
    if (sub2) {
        rep(i, c) {
            processed.clear();
            processed.resize(R, vb(C, false));
            sub2calc(i);
        }
    }
    if (sub3) {
        s3dp.resize(r, v2i(c, vi(2)));
        rep(i, r) {
            s3update(i);
            //cout << "Initial dp update " << i << "\n";
        }
    }
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    if (sub3) {
        rept(i, P, r) {
            s3update(i);
            //cout << "dp update " << i << "\n";
        }
    }
    sub2 = false;
}

void changeV(int P, int Q, int W) {
    totw += W - v[P][Q];
    v[P][Q] = W;
    if (sub3) {
        rept(i, P+1, r) {
            s3update(i);
            //cout << "dp update " << i << "\n";
        }
    }
    sub2 = false;
}

int escape(int V1, int V2) {
    if (sub1) {
        return totw;
    }
    if (sub2) {
        
        return mindists[V1][V2];
    }
    if (sub3) {
        return s3dp[r - 1][V2][V1];
    }
    if (sub4) {
        //cout << "sub4\n";
        processed.clear();
        processed.resize(r, vb(c, false));
        mindist4(V1, V2);
    }
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void s3update(int)':
wombats.cpp:41:9: warning: unused variable 's' [-Wunused-variable]
   41 |     int s, c;
      |         ^
wombats.cpp:41:12: warning: unused variable 'c' [-Wunused-variable]
   41 |     int s, c;
      |            ^
wombats.cpp: In function 'int mindist4(int, int)':
wombats.cpp:96:10: warning: control reaches end of non-void function [-Wreturn-type]
   96 |     djpq q;
      |          ^
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:226:1: warning: control reaches end of non-void function [-Wreturn-type]
  226 | }
      | ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4892 KB Output is correct
2 Correct 3 ms 5148 KB Output is correct
3 Correct 44 ms 7700 KB Output is correct
4 Correct 2 ms 4984 KB Output is correct
5 Correct 3 ms 5148 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2524 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 82 ms 4660 KB Output is correct
12 Correct 2 ms 2396 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 253 ms 7388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9560 KB Output is correct
2 Correct 23 ms 9624 KB Output is correct
3 Correct 16 ms 9816 KB Output is correct
4 Correct 50 ms 10824 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 294 ms 7404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 250 ms 7504 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -