oj.uz

Submission #251227

# Submission time Handle Problem Language Result Execution time Memory
251227 2020-07-20T15:50:14 Z AaronNaidu Wombats (IOI13_wombats) C++14
21 / 100
 20000 ms 33088 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[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];
}

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: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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 27984 KB Output is correct
2 Correct 18 ms 27904 KB Output is correct
3 Correct 114 ms 30100 KB Output is correct
4 Correct 18 ms 27904 KB Output is correct
5 Correct 21 ms 27980 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 13 ms 23836 KB Output is correct
8 Correct 15 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 36 ms 23936 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 32 ms 23936 KB Output is correct
7 Correct 35 ms 23936 KB Output is correct
8 Correct 35 ms 23936 KB Output is correct
9 Correct 36 ms 23936 KB Output is correct
10 Correct 36 ms 23936 KB Output is correct
11 Correct 11349 ms 25448 KB Output is correct
12 Correct 40 ms 23936 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 24696 KB Output is correct
2 Correct 247 ms 24696 KB Output is correct
3 Correct 216 ms 24740 KB Output is correct
4 Correct 210 ms 24576 KB Output is correct
5 Incorrect 222 ms 24644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 32116 KB Output is correct
2 Correct 1058 ms 32128 KB Output is correct
3 Correct 604 ms 32120 KB Output is correct
4 Execution timed out 20014 ms 33088 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 24576 KB Output is correct
2 Correct 232 ms 24696 KB Output is correct
3 Correct 220 ms 24696 KB Output is correct
4 Correct 216 ms 24576 KB Output is correct
5 Incorrect 210 ms 24568 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 24700 KB Output is correct
2 Correct 232 ms 24704 KB Output is correct
3 Correct 215 ms 24576 KB Output is correct
4 Correct 215 ms 24696 KB Output is correct
5 Incorrect 210 ms 24576 KB Output isn't correct
6 Halted 0 ms 0 KB -