oj.uz

Submission #413538

# Submission time Handle Problem Language Result Execution time Memory
413538 2021-05-28T21:03:37 Z LouayFarah Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 9232 KB 
#include "bits/stdc++.h"
#include "wombats.h"
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
int r, c;
vector<vector<int>> h, v;
 
void init(int R, int C, int H[5000][200], int V[5000][200])
{
    r = R;
    c = C;
 
    h.resize(R);
    for(int i = 0; i<R; i++)
        h[i].resize(C-1);
 
    v.resize(R-1);
    for(int i = 0; i<R-1; i++)
        v[i].resize(C);
 
    for(int i = 0; i<r; i++)
    {
        for(int j = 0; j<c-1; j++)
        {
            h[i][j] = H[i][j];
        }
    }
 
    for(int i = 0; i<r-1; i++)
    {
        for(int j = 0; j<c; j++)
        {
            v[i][j] = V[i][j];
        }
    }
}
 
void changeH(int P, int Q, int W)
{
    h[P][Q] = W;
}
 
void changeV(int P, int Q, int W)
{
    v[P][Q] = W;
}
 
int escape(int V1, int V2)
{
  	if(c==1)
    {
      	int sum = 0;
      	for(int i = 0; i<r-1; i++)
        {
          	sum+=v[i][0];
        }
      	return sum;
    }
    V2+=(r-1)*c;
    vector<bool> visited(r*c, false);
    vector<int> dist(r*c, 1e8);
 
    priority_queue<pair<int, int>> pq;
    pq.push(mp(0, V1));
    dist[V1] = false;
 
    while(!pq.empty())
    {
        int u = pq.top().se;
        pq.pop();
        if(visited[u])
            continue;
        visited[u] = true;
 
        if((u%c)>0)
        {
            int b = u-1;
            int w = h[b/c][b%c];
 
            if(dist[u]+w<dist[b])
            {
                dist[b] =  dist[u]+w;
                pq.push(mp(-dist[b], b));
            }
 
        }
        if((u%c)<c-1)
        {
            int b = u+1;
            int w = h[u/c][u%c];
            if(dist[u]+w<dist[b])
            {
                dist[b] =  dist[u]+w;
                pq.push(mp(-dist[b], b));
            }
        }
        if((u-(r-1)*c)<0)
        {
            int b = u+c;
            int w = v[u/c][u%c];
            if(dist[u]+w<dist[b])
            {
                dist[b] =  dist[u]+w;
                pq.push(mp(-dist[b], b));
            }
        }
    }
 
    return dist[V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4556 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 1151 ms 6544 KB Output is correct
4 Correct 7 ms 4556 KB Output is correct
5 Correct 7 ms 4556 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 23 ms 332 KB Output is correct
5 Correct 11 ms 332 KB Output is correct
6 Correct 13 ms 348 KB Output is correct
7 Correct 23 ms 332 KB Output is correct
8 Correct 15 ms 344 KB Output is correct
9 Correct 18 ms 332 KB Output is correct
10 Correct 16 ms 340 KB Output is correct
11 Correct 8814 ms 1456 KB Output is correct
12 Correct 24 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 588 KB Output is correct
2 Correct 225 ms 800 KB Output is correct
3 Correct 153 ms 588 KB Output is correct
4 Correct 153 ms 588 KB Output is correct
5 Correct 149 ms 600 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 229 ms 616 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 8780 KB Output is correct
2 Correct 1262 ms 8852 KB Output is correct
3 Correct 586 ms 8736 KB Output is correct
4 Execution timed out 20005 ms 9148 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 708 KB Output is correct
2 Correct 225 ms 700 KB Output is correct
3 Correct 150 ms 608 KB Output is correct
4 Correct 152 ms 620 KB Output is correct
5 Correct 152 ms 604 KB Output is correct
6 Correct 593 ms 8728 KB Output is correct
7 Correct 1279 ms 8732 KB Output is correct
8 Correct 587 ms 8724 KB Output is correct
9 Execution timed out 20057 ms 9216 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 588 KB Output is correct
2 Correct 228 ms 700 KB Output is correct
3 Correct 153 ms 588 KB Output is correct
4 Correct 151 ms 608 KB Output is correct
5 Correct 152 ms 604 KB Output is correct
6 Correct 585 ms 8732 KB Output is correct
7 Correct 1279 ms 8860 KB Output is correct
8 Correct 592 ms 8772 KB Output is correct
9 Execution timed out 20047 ms 9232 KB Time limit exceeded
10 Halted 0 ms 0 KB -