Submission #123079

#	Time	Username	Problem	Language	Result	Execution time	Memory
123079		Mahdi_Jfri	Wombats (IOI13_wombats)	C++14	55 / 100	778 ms	262144 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24