oj.uz

Submission #123079

# Submission time Handle Problem Language Result Execution time Memory
123079 2019-06-30T07:42:17 Z Mahdi_Jfri Wombats (IOI13_wombats) C++14
55 / 100
 778 ms 262144 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 idH[maxn][maxm] , idV[maxn][maxm] , id;

int from[maxe] , to[maxe] , w[maxe] , n , m;

vector<int> adj[maxv];
int d[maxm][maxv];

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] + w[idH[i][j]]);
			d[src][v] = min(d[src][v] , d[src][u] + w[idH[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] + w[idH[i][j]]);
			d[src][v] = min(d[src][v] , d[src][u] + w[idH[i][j]]);
		}

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

void build()
{
	for(int i = 0; i < m; i++)
		dij(i);
}

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++)
		{
			int a = cd(i , j) , b = cd(i , j + 1);
			
			adj[a].pb(id);
			adj[b].pb(id);
			from[id] = a , to[id] = b , w[id] = H[i][j];

			idH[i][j] = id++;
		}

	for(int i = 0; i + 1 < n; i++)
		for(int j = 0; j < m; j++)
		{
			int a = cd(i , j) , b = cd(i + 1 , j);

			adj[a].pb(id);
			from[id] = a , to[id] = b , w[id] = V[i][j];
			idV[i][j] = id++;
		}

	build();
}

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

void changeV(int P, int Q, int W)
{
	int e = idV[P][Q];
	w[e] = 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 100 ms 23416 KB Output is correct
2 Correct 97 ms 23416 KB Output is correct
3 Correct 172 ms 24952 KB Output is correct
4 Correct 101 ms 23416 KB Output is correct
5 Correct 101 ms 23288 KB Output is correct
6 Correct 17 ms 16888 KB Output is correct
7 Correct 16 ms 16888 KB Output is correct
8 Correct 16 ms 16888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16964 KB Output is correct
2 Correct 16 ms 16856 KB Output is correct
3 Correct 16 ms 16888 KB Output is correct
4 Correct 52 ms 61688 KB Output is correct
5 Correct 53 ms 61748 KB Output is correct
6 Correct 52 ms 61816 KB Output is correct
7 Correct 52 ms 61792 KB Output is correct
8 Correct 51 ms 59384 KB Output is correct
9 Correct 52 ms 61816 KB Output is correct
10 Correct 51 ms 59356 KB Output is correct
11 Correct 128 ms 62712 KB Output is correct
12 Correct 53 ms 61816 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 251176 KB Output is correct
2 Correct 263 ms 248812 KB Output is correct
3 Correct 265 ms 251212 KB Output is correct
4 Correct 269 ms 251128 KB Output is correct
5 Correct 287 ms 248888 KB Output is correct
6 Correct 16 ms 16888 KB Output is correct
7 Correct 16 ms 16888 KB Output is correct
8 Correct 16 ms 16892 KB Output is correct
9 Correct 228 ms 251024 KB Output is correct
10 Correct 27 ms 23932 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 32376 KB Output is correct
2 Correct 249 ms 32248 KB Output is correct
3 Correct 248 ms 32248 KB Output is correct
4 Correct 289 ms 33020 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 251224 KB Output is correct
2 Correct 263 ms 248696 KB Output is correct
3 Correct 265 ms 251220 KB Output is correct
4 Correct 265 ms 251128 KB Output is correct
5 Correct 262 ms 248696 KB Output is correct
6 Correct 248 ms 32376 KB Output is correct
7 Correct 254 ms 32376 KB Output is correct
8 Correct 265 ms 32248 KB Output is correct
9 Correct 288 ms 33148 KB Output is correct
10 Correct 96 ms 23416 KB Output is correct
11 Correct 95 ms 23288 KB Output is correct
12 Correct 167 ms 24952 KB Output is correct
13 Correct 99 ms 23420 KB Output is correct
14 Correct 99 ms 23256 KB Output is correct
15 Correct 16 ms 16888 KB Output is correct
16 Correct 16 ms 16888 KB Output is correct
17 Correct 16 ms 16888 KB Output is correct
18 Correct 52 ms 61688 KB Output is correct
19 Correct 53 ms 61688 KB Output is correct
20 Correct 52 ms 61688 KB Output is correct
21 Correct 52 ms 61688 KB Output is correct
22 Correct 51 ms 59384 KB Output is correct
23 Correct 53 ms 61816 KB Output is correct
24 Correct 51 ms 59468 KB Output is correct
25 Correct 130 ms 62872 KB Output is correct
26 Correct 53 ms 61688 KB Output is correct
27 Correct 230 ms 251100 KB Output is correct
28 Runtime error 778 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 251248 KB Output is correct
2 Correct 280 ms 248788 KB Output is correct
3 Correct 264 ms 251128 KB Output is correct
4 Correct 266 ms 251184 KB Output is correct
5 Correct 262 ms 248844 KB Output is correct
6 Correct 245 ms 32248 KB Output is correct
7 Correct 259 ms 32248 KB Output is correct
8 Correct 249 ms 32376 KB Output is correct
9 Correct 294 ms 32988 KB Output is correct
10 Correct 107 ms 23416 KB Output is correct
11 Correct 98 ms 23384 KB Output is correct
12 Correct 170 ms 25084 KB Output is correct
13 Correct 101 ms 23288 KB Output is correct
14 Correct 97 ms 23288 KB Output is correct
15 Runtime error 388 ms 100600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -