제출 #251227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251227		AaronNaidu	웜뱃 (IOI13_wombats)	C++14	21 / 100	20014 ms	33088 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;

int r, c;
int h[5000][200], v[5000][200];
int prefSums[5000];
int dists[1000000];
bool visited[1000000];
priority_queue<pair<int, int> > q;
vector<pair<int, int> > graph[1000000];

void changeH(int p, int q, int w) {
    for (int i = 0; i < graph[c*p+q].size(); i++)
    {
        if (graph[c*p+q][i].first == c*p+q+1)
        {
            //cout << "Change H part 1:" << graph[c*p+q][i].second << "\n";
            graph[c*p+q][i].second = w;
            //cout << "Changed to " << graph[c*p+q][i].second << "\n";
        }
    }
    for (int i = 0; i < graph[c*p+q+1].size(); i++)
    {
        if (graph[c*p+q+1][i].first == c*p+q)
        {
            //cout << "Change H part 2:" << graph[c*p+q+1][i].second << "\n";
            graph[c*p+q+1][i].second = w;
            //cout << "Changed to " << graph[c*p+q+1][i].second << "\n";
        }
        
    }
}

void changeV(int p, int q, int w){
    if (c == 1)
    {
        int diff = w - (prefSums[p+1] - prefSums[p]);
        for (int i = p+1; i < r; i++)
        {
            prefSums[i] += diff;
        }
        return;
    }
    
    for (int i = 0; i < graph[i*p+q].size(); i++)
    {
        if (graph[c*p+q][i].first == c*p+ c + q)
        {
           //cout << "Change V: " << graph[c*p+q][i].second << "\n";
           graph[c*p+q][i].second = w;
           //cout << "Changed to " << graph[c*p+q][i].second << "\n";
        }
        
    }
    
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R;
    c = C;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c-1; j++)
        {
            graph[i * c + j].push_back({i*c+j+1, H[i][j]});
            graph[i*c + j+1].push_back({i*c+j, H[i][j]});
            //cout << "Constructing graph\n";
        }
    }
    for (int i = 0; i < r-1; i++)
    {
        for (int j = 0; j < c; j++)
        {
            graph[i*c+j].push_back({i*c + c + j,V[i][j]});
            //cout << "Constructing graph\n";
        }
    }
    if (c == 1)
    {
        for (int i = 1; i < r; i++)
        {
            prefSums[i] = prefSums[i-1] + V[i-1][0];
        }
        
    }
    
}

int escape(int v1, int v2) {
    if (c == 1)
    {
        return prefSums[r-1];
    }
    
    int startNode = v1;
    int endNode = c*(r-1)+v2;
    //cout << "Going from " << startNode << " to " << endNode << "\n";
    for (int i = 0; i < r * c; i++)
    {
        dists[i] = 1000000000;
        visited[i] = false;
    }
    q.push({0, startNode});
    dists[startNode] = 0;
    while (!q.empty())
    {
        //cout << "in BFS\n";
        int dist = q.top().first;
        int node = q.top().second;
        //cout << "At node " << node << " at dist " << dist << "\n";
        q.pop();
        if (!visited[node])
        {
            visited[node] = true;
            dists[node] = min(-dist, dists[node]);
            for (auto i : graph[node])
            {
                if (!visited[i.first])
                {
                    q.push({dist-i.second, i.first});
                    //cout << "Pushing " << i.first << " at dist " << dist-i.second << "\n";
                }
            }
        }
    }
    return dists[endNode];
}

컴파일 시 표준 에러 (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:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[c*p+q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~
wombats.cpp:23:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[c*p+q+1].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[i*p+q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24