oj.uz

Submission #123065

# Submission time Handle Problem Language Result Execution time Memory
123065 2019-06-30T07:18:19 Z Mahdi_Jfri Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 251360 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;
	set<pair<int , int> > st;
	st.insert({0 , src});

	while(!st.empty())
	{
		int v = st.begin() -> second , W = st.begin() -> first;
		st.erase(st.begin());
		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.insert({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 215 ms 23416 KB Output is correct
2 Correct 213 ms 23416 KB Output is correct
3 Correct 284 ms 26100 KB Output is correct
4 Correct 211 ms 23416 KB Output is correct
5 Correct 214 ms 23416 KB Output is correct
6 Correct 17 ms 16888 KB Output is correct
7 Correct 17 ms 16860 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 16804 KB Output is correct
2 Correct 16 ms 16892 KB Output is correct
3 Correct 16 ms 16888 KB Output is correct
4 Correct 55 ms 61692 KB Output is correct
5 Correct 54 ms 61688 KB Output is correct
6 Correct 64 ms 61816 KB Output is correct
7 Correct 63 ms 61944 KB Output is correct
8 Correct 53 ms 59420 KB Output is correct
9 Correct 55 ms 61816 KB Output is correct
10 Correct 53 ms 59384 KB Output is correct
11 Correct 132 ms 64168 KB Output is correct
12 Correct 57 ms 61816 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20115 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 1092 ms 32384 KB Output is correct
2 Correct 1608 ms 32480 KB Output is correct
3 Correct 1079 ms 32376 KB Output is correct
4 Correct 1128 ms 33620 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20105 ms 251360 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 20088 ms 251200 KB Time limit exceeded
2 Halted 0 ms 0 KB -