oj.uz

Submission #123071

# Submission time Handle Problem Language Result Execution time Memory
123071 2019-06-30T07:26:45 Z Mahdi_Jfri Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 251256 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;
	priority_queue<pair<int , int> > st;
	st.push({0 , src});

	while(!st.empty())
	{
		int v = st.top().second , W = -st.top().first;
		st.pop();
		if(d[src][v] != W)
			continue;

		for(auto e : adj[v])
		{
			int u = from[e] ^ to[e] ^ v;
			if(d[src][u] > d[src][v] + w[e])
			{
				d[src][u] = d[src][v] + w[e];
				st.push({-d[src][u] , u});
			}
		}
	}
}

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 146 ms 23288 KB Output is correct
2 Correct 146 ms 23292 KB Output is correct
3 Correct 231 ms 24952 KB Output is correct
4 Correct 144 ms 23416 KB Output is correct
5 Correct 143 ms 23388 KB Output is correct
6 Correct 19 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 16888 KB Output is correct
3 Correct 16 ms 16888 KB Output is correct
4 Correct 55 ms 61688 KB Output is correct
5 Correct 53 ms 61816 KB Output is correct
6 Correct 57 ms 61752 KB Output is correct
7 Correct 54 ms 61788 KB Output is correct
8 Correct 52 ms 59356 KB Output is correct
9 Correct 55 ms 61816 KB Output is correct
10 Correct 52 ms 59384 KB Output is correct
11 Correct 129 ms 62792 KB Output is correct
12 Correct 55 ms 61816 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20080 ms 251256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 32248 KB Output is correct
2 Correct 1410 ms 32380 KB Output is correct
3 Correct 651 ms 32312 KB Output is correct
4 Correct 714 ms 33060 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20059 ms 251128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20057 ms 251132 KB Time limit exceeded
2 Halted 0 ms 0 KB -