oj.uz

Submission #123078

# Submission time Handle Problem Language Result Execution time Memory
123078 2019-06-30T07:38:59 Z Mahdi_Jfri Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 251328 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];

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

void dij(int src)
{
	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;
	build();
}

void changeV(int P, int Q, int W)
{
	int e = idV[P][Q];
	w[e] = W;
	build();
}

int escape(int V1, int V2)
{
	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 97 ms 23416 KB Output is correct
2 Correct 97 ms 23388 KB Output is correct
3 Correct 171 ms 24952 KB Output is correct
4 Correct 102 ms 23416 KB Output is correct
5 Correct 99 ms 23288 KB Output is correct
6 Correct 18 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 16888 KB Output is correct
2 Correct 16 ms 16840 KB Output is correct
3 Correct 16 ms 16888 KB Output is correct
4 Correct 52 ms 61816 KB Output is correct
5 Correct 53 ms 61748 KB Output is correct
6 Correct 53 ms 61816 KB Output is correct
7 Correct 52 ms 61788 KB Output is correct
8 Correct 51 ms 59420 KB Output is correct
9 Correct 53 ms 61816 KB Output is correct
10 Correct 51 ms 59384 KB Output is correct
11 Correct 128 ms 62756 KB Output is correct
12 Correct 61 ms 61816 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5572 ms 251220 KB Output is correct
2 Correct 5251 ms 248824 KB Output is correct
3 Correct 5332 ms 251248 KB Output is correct
4 Correct 5269 ms 251252 KB Output is correct
5 Correct 5166 ms 248800 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 16888 KB Output is correct
9 Execution timed out 20022 ms 251128 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 32376 KB Output is correct
2 Correct 257 ms 32276 KB Output is correct
3 Correct 250 ms 32376 KB Output is correct
4 Correct 302 ms 33172 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5238 ms 251164 KB Output is correct
2 Correct 5478 ms 248952 KB Output is correct
3 Correct 5414 ms 251220 KB Output is correct
4 Correct 5409 ms 251328 KB Output is correct
5 Correct 5318 ms 248900 KB Output is correct
6 Correct 263 ms 32384 KB Output is correct
7 Correct 252 ms 32364 KB Output is correct
8 Correct 253 ms 32376 KB Output is correct
9 Correct 299 ms 33784 KB Output is correct
10 Correct 105 ms 23416 KB Output is correct
11 Correct 99 ms 23416 KB Output is correct
12 Correct 175 ms 26232 KB Output is correct
13 Correct 106 ms 23416 KB Output is correct
14 Correct 99 ms 23412 KB Output is correct
15 Correct 17 ms 17016 KB Output is correct
16 Correct 19 ms 16888 KB Output is correct
17 Correct 16 ms 16888 KB Output is correct
18 Correct 52 ms 61716 KB Output is correct
19 Correct 53 ms 61816 KB Output is correct
20 Correct 53 ms 61688 KB Output is correct
21 Correct 61 ms 61816 KB Output is correct
22 Correct 51 ms 59384 KB Output is correct
23 Correct 57 ms 61816 KB Output is correct
24 Correct 53 ms 59512 KB Output is correct
25 Correct 128 ms 64172 KB Output is correct
26 Correct 52 ms 61688 KB Output is correct
27 Execution timed out 20084 ms 251128 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5248 ms 251240 KB Output is correct
2 Correct 5387 ms 248832 KB Output is correct
3 Correct 5329 ms 251256 KB Output is correct
4 Correct 5272 ms 251256 KB Output is correct
5 Correct 5916 ms 248852 KB Output is correct
6 Correct 267 ms 32476 KB Output is correct
7 Correct 248 ms 32376 KB Output is correct
8 Correct 249 ms 32248 KB Output is correct
9 Correct 296 ms 33812 KB Output is correct
10 Correct 99 ms 23288 KB Output is correct
11 Correct 96 ms 23288 KB Output is correct
12 Correct 166 ms 26104 KB Output is correct
13 Correct 100 ms 23544 KB Output is correct
14 Correct 96 ms 23416 KB Output is correct
15 Runtime error 377 ms 110328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -