oj.uz

답안 #251231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251231 2020-07-20T15:55:45 Z AaronNaidu 웜뱃 (IOI13_wombats) C++14
9 / 100
 20000 ms 262148 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

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 27904 KB Output is correct
2 Correct 18 ms 27904 KB Output is correct
3 Correct 101 ms 30200 KB Output is correct
4 Correct 19 ms 27904 KB Output is correct
5 Correct 19 ms 27904 KB Output is correct
6 Correct 15 ms 23808 KB Output is correct
7 Correct 14 ms 23840 KB Output is correct
8 Correct 14 ms 23808 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Correct 14 ms 23936 KB Output is correct
4 Correct 39 ms 23904 KB Output is correct
5 Correct 22 ms 23936 KB Output is correct
6 Runtime error 3596 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 675 ms 24696 KB Output is correct
2 Correct 249 ms 24952 KB Output is correct
3 Correct 615 ms 24712 KB Output is correct
4 Correct 549 ms 24576 KB Output is correct
5 Incorrect 546 ms 24696 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3772 ms 32248 KB Output is correct
2 Correct 1072 ms 32120 KB Output is correct
3 Correct 10194 ms 32152 KB Output is correct
4 Execution timed out 20067 ms 32496 KB Time limit exceeded

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 690 ms 24824 KB Output is correct
2 Correct 249 ms 24840 KB Output is correct
3 Correct 598 ms 24824 KB Output is correct
4 Correct 541 ms 24576 KB Output is correct
5 Incorrect 533 ms 24672 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 694 ms 24696 KB Output is correct
2 Correct 258 ms 24952 KB Output is correct
3 Correct 592 ms 24692 KB Output is correct
4 Correct 534 ms 24692 KB Output is correct
5 Incorrect 570 ms 24672 KB Output isn't correct
6 Halted 0 ms 0 KB -