oj.uz

Submission #123081

# Submission time Handle Problem Language Result Execution time Memory
123081 2019-06-30T07:46:23 Z Mahdi_Jfri Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 252388 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e3 + 20;
const int maxm = 1e2 + 20;
const int maxv = maxn * maxm;
const int maxe = maxn * maxm * 2;

int wH[maxn][maxm] , wV[maxn][maxm] , id;

int d[maxm][maxv] , n , m;
bool have[maxm];

int cd(int a , int b)
{
	return a * m + b;
}

void dij(int src)
{
	if(have[src])
		return;

	have[src] = 1;
	memset(d[src] , 63 , sizeof d[src]);
	d[src][src] = 0;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j + 1 < m; j++)
		{
			int v = cd(i , j) , u = cd(i , j + 1);
			d[src][u] = min(d[src][u] , d[src][v] + wH[i][j]);
			d[src][v] = min(d[src][v] , d[src][u] + wH[i][j]);
		}

		for(int j = m - 2; j >= 0; j--)
		{
			int v = cd(i , j) , u = cd(i , j + 1);
			d[src][u] = min(d[src][u] , d[src][v] + wH[i][j]);
			d[src][v] = min(d[src][v] , d[src][u] + wH[i][j]);
		}

		if(i + 1 < n)
			for(int j = 0; j < m; j++)
				d[src][cd(i + 1 , j)] = d[src][cd(i , j)] + wV[i][j];
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
	n = R , m = C;

	for(int i = 0; i < n; i++)
		for(int j = 0; j + 1 < m; j++)
			wH[i][j] = H[i][j];	

	for(int i = 0; i + 1 < n; i++)
		for(int j = 0; j < m; j++)
			wV[i][j] = V[i][j];
}

void changeH(int P, int Q, int W)
{
	wH[P][Q] = W;
	memset(have , 0 , sizeof have);
}

void changeV(int P, int Q, int W)
{
	wV[P][Q] = W;
	memset(have , 0 , sizeof have);
}

int escape(int V1, int V2)
{
	dij(V1);
	return d[V1][cd(n - 1 , V2)];
}

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;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 9080 KB Output is correct
2 Correct 86 ms 9032 KB Output is correct
3 Correct 155 ms 10692 KB Output is correct
4 Correct 81 ms 8956 KB Output is correct
5 Correct 82 ms 9080 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 40 ms 47480 KB Output is correct
5 Correct 40 ms 47536 KB Output is correct
6 Correct 40 ms 47608 KB Output is correct
7 Correct 39 ms 47608 KB Output is correct
8 Correct 37 ms 45128 KB Output is correct
9 Correct 40 ms 47608 KB Output is correct
10 Correct 38 ms 45176 KB Output is correct
11 Correct 116 ms 48504 KB Output is correct
12 Correct 40 ms 47612 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 161080 KB Output is correct
2 Correct 140 ms 144640 KB Output is correct
3 Correct 162 ms 149320 KB Output is correct
4 Correct 171 ms 151716 KB Output is correct
5 Correct 174 ms 151652 KB Output is correct
6 Correct 9 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 20 ms 5368 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 17608 KB Output is correct
2 Correct 226 ms 17644 KB Output is correct
3 Correct 225 ms 17528 KB Output is correct
4 Correct 270 ms 18416 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 161036 KB Output is correct
2 Correct 153 ms 144656 KB Output is correct
3 Correct 150 ms 149332 KB Output is correct
4 Correct 147 ms 151692 KB Output is correct
5 Correct 165 ms 151668 KB Output is correct
6 Correct 242 ms 17604 KB Output is correct
7 Correct 228 ms 17528 KB Output is correct
8 Correct 231 ms 17656 KB Output is correct
9 Correct 277 ms 18364 KB Output is correct
10 Correct 88 ms 8952 KB Output is correct
11 Correct 82 ms 8952 KB Output is correct
12 Correct 151 ms 10616 KB Output is correct
13 Correct 82 ms 9000 KB Output is correct
14 Correct 82 ms 8996 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 40 ms 47480 KB Output is correct
19 Correct 40 ms 47480 KB Output is correct
20 Correct 40 ms 47480 KB Output is correct
21 Correct 40 ms 47556 KB Output is correct
22 Correct 38 ms 45176 KB Output is correct
23 Correct 40 ms 47608 KB Output is correct
24 Correct 38 ms 45228 KB Output is correct
25 Correct 116 ms 48604 KB Output is correct
26 Correct 40 ms 47480 KB Output is correct
27 Correct 19 ms 5368 KB Output is correct
28 Execution timed out 20078 ms 252388 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 161016 KB Output is correct
2 Correct 142 ms 144576 KB Output is correct
3 Correct 143 ms 149368 KB Output is correct
4 Correct 146 ms 151672 KB Output is correct
5 Correct 146 ms 151644 KB Output is correct
6 Correct 229 ms 17656 KB Output is correct
7 Correct 244 ms 17528 KB Output is correct
8 Correct 231 ms 17528 KB Output is correct
9 Correct 265 ms 18424 KB Output is correct
10 Correct 82 ms 8952 KB Output is correct
11 Correct 86 ms 8952 KB Output is correct
12 Correct 155 ms 10488 KB Output is correct
13 Correct 82 ms 8952 KB Output is correct
14 Correct 81 ms 8952 KB Output is correct
15 Runtime error 264 ms 33912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -