oj.uz

Submission #251216

# Submission time Handle Problem Language Result Execution time Memory
251216 2020-07-20T15:35:00 Z AaronNaidu Wombats (IOI13_wombats) C++14
12 / 100
 20000 ms 33060 KB 
#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;

int r, c;
int h[5000][200], v[5000][200];
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){
    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";
        }
    }
    
}

int escape(int v1, int v2) {
    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];
}

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 27904 KB Output is correct
2 Correct 81 ms 27904 KB Output is correct
3 Execution timed out 20069 ms 30476 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 14 ms 23936 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 36 ms 23936 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Correct 32 ms 23936 KB Output is correct
7 Correct 33 ms 23936 KB Output is correct
8 Correct 35 ms 23936 KB Output is correct
9 Correct 38 ms 23936 KB Output is correct
10 Correct 34 ms 23936 KB Output is correct
11 Correct 11274 ms 26376 KB Output is correct
12 Correct 37 ms 23936 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 24772 KB Output is correct
2 Correct 237 ms 24704 KB Output is correct
3 Correct 220 ms 24696 KB Output is correct
4 Correct 223 ms 24576 KB Output is correct
5 Incorrect 220 ms 24576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 32120 KB Output is correct
2 Correct 1065 ms 32120 KB Output is correct
3 Correct 619 ms 32248 KB Output is correct
4 Execution timed out 20035 ms 33060 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 24696 KB Output is correct
2 Correct 237 ms 24704 KB Output is correct
3 Correct 225 ms 24576 KB Output is correct
4 Correct 218 ms 24576 KB Output is correct
5 Incorrect 218 ms 24576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 24576 KB Output is correct
2 Correct 241 ms 24824 KB Output is correct
3 Correct 219 ms 24576 KB Output is correct
4 Correct 212 ms 24576 KB Output is correct
5 Incorrect 214 ms 24696 KB Output isn't correct
6 Halted 0 ms 0 KB -