oj.uz

Submission #251260

# Submission time Handle Problem Language Result Execution time Memory
251260 2020-07-20T16:20:18 Z AaronNaidu Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 37648 KB 
#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 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";
        }
        
    }
}
 
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";
        }
        
    }
    
}
 
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";
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            dists[i][j] = 1000000000;
            visited[i][j] = false;
        }
        
    }
    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";
                }
            }
        }
    }
    return dists[endNode.first][endNode.second];
}

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:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[p][q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~
wombats.cpp:24: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:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graph[p][q].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27904 KB Output is correct
2 Correct 19 ms 27904 KB Output is correct
3 Correct 96 ms 30712 KB Output is correct
4 Correct 18 ms 27904 KB Output is correct
5 Correct 20 ms 27904 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 14 ms 23808 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 45 ms 23976 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 40 ms 23936 KB Output is correct
7 Correct 37 ms 23936 KB Output is correct
8 Correct 36 ms 23936 KB Output is correct
9 Correct 39 ms 23936 KB Output is correct
10 Correct 37 ms 23936 KB Output is correct
11 Correct 12780 ms 26720 KB Output is correct
12 Correct 38 ms 23936 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 24860 KB Output is correct
2 Correct 279 ms 25000 KB Output is correct
3 Correct 254 ms 24880 KB Output is correct
4 Correct 262 ms 24952 KB Output is correct
5 Correct 240 ms 24824 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 14 ms 23808 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct
9 Correct 262 ms 24952 KB Output is correct
10 Correct 14 ms 23808 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 831 ms 36964 KB Output is correct
2 Correct 1343 ms 36956 KB Output is correct
3 Correct 848 ms 36984 KB Output is correct
4 Execution timed out 20034 ms 37648 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 24864 KB Output is correct
2 Correct 279 ms 24960 KB Output is correct
3 Correct 273 ms 24832 KB Output is correct
4 Correct 241 ms 24832 KB Output is correct
5 Correct 253 ms 24828 KB Output is correct
6 Correct 869 ms 36984 KB Output is correct
7 Correct 1405 ms 37112 KB Output is correct
8 Correct 894 ms 37088 KB Output is correct
9 Execution timed out 20057 ms 37528 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 24832 KB Output is correct
2 Correct 311 ms 24960 KB Output is correct
3 Correct 256 ms 24824 KB Output is correct
4 Correct 258 ms 24832 KB Output is correct
5 Correct 246 ms 24832 KB Output is correct
6 Correct 919 ms 36984 KB Output is correct
7 Correct 1398 ms 36952 KB Output is correct
8 Correct 887 ms 36972 KB Output is correct
9 Execution timed out 20078 ms 37512 KB Time limit exceeded
10 Halted 0 ms 0 KB -