Submission #251268

#	Time	Username	Problem	Language	Result	Execution time	Memory
251268		AaronNaidu	Wombats (IOI13_wombats)	C++14	27 / 100	20041 ms	38300 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[5000][200];
int bigDists[200][200];
bool visited[5000][200];
priority_queue<pair<int, pair<int, int> > > q;
vector<pair<pair<int, int> , int> > graph[5000][200];

void distsFromCol(int x) {
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            dists[i][j] = 1000000000;
            visited[i][j] = false;
        } 
    }
    pair<int, int> startNode = {0, x};
    q.push({0, startNode});
    dists[startNode.first][startNode.second] = 0;
    while (!q.empty())
    {
        //cout << "in BFS\n";
        int dist = q.top().first;
        int nodex = q.top().second.first;
        int nodey = q.top().second.second;
        //cout << "At node " << node << " at dist " << dist << "\n";
        q.pop();
        if (!visited[nodex][nodey])
        {
            visited[nodex][nodey] = true;
            dists[nodex][nodey] = min(-dist, dists[nodex][nodey]);
            for (auto i : graph[nodex][nodey])
            {
                if (!visited[i.first.first][i.first.second])
                {
                    q.push({dist-i.second, {i.first.first, i.first.second}});
                    //cout << "Pushing " << i.first << " at dist " << dist-i.second << "\n";
                }
            }
        }
    }
    for (int i = 0; i < c; i++)
    {
        bigDists[x][i] = dists[r-1][i];
    }
    
}

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

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[p][q].size(); i++)
    {
        if (graph[p][q][i].first.first == p+1 and graph[p][q][i].first.second == q)
        {
           //cout << "Change V: " << graph[c*p+q][i].second << "\n";
           graph[p][q][i].second = w;
           //cout << "Changed to " << graph[c*p+q][i].second << "\n";
        }
        
    }
    for (int i = 0; i < c; i++)
    {
        distsFromCol(i);
    }
    
}

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][j].push_back({{i,j+1}, H[i][j]});
            graph[i][j+1].push_back({{i,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][j].push_back({{i+1,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];
    }
    
    pair<int, int> startNode = {0, v1};
    pair<int, int> endNode = {(r-1),v2};
    //cout << "Going from " << startNode << " to " << endNode << "\n";
    return bigDists[v1][v2];
}

Compilation message (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:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[p][q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~
wombats.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[p][q+1].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[p][q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:145:20: warning: variable 'startNode' set but not used [-Wunused-but-set-variable]
     pair<int, int> startNode = {0, v1};
                    ^~~~~~~~~
wombats.cpp:146:20: warning: variable 'endNode' set but not used [-Wunused-but-set-variable]
     pair<int, int> endNode = {(r-1),v2};
                    ^~~~~~~

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