oj.uz

답안 #1012527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012527 2024-07-02T09:29:39 Z parsadox2 웜뱃 (IOI13_wombats) C++17
39 / 100
 20000 ms 35760 KB 
#include <bits/stdc++.h>
#include "wombats.h"
#pragma GCC optimize("unroll-loops,Ofast,O3")
#define F first
#define S second
using namespace std;
 
const int N = 5e3 + 10 , M = 2e2 + 10 , Sq = 200 , inf = 1e9 + 10 , TOF = N / Sq + 10;
 
int r , c , h[N][M] , v[N][M] , nex[TOF][M][M] , adj[M][M] , ans[M][M] , dis[N][M] , dis2[TOF][M] , las;
bool is_update , marked[N][M];
 
void Dij(int num , int Qs)
{
	int Ps = num * Sq , R = min(r - 1 , Ps + Sq);
	las = max(las , num);
	for(int i = Ps ; i <= R ; i++)  for(int j = 0 ; j < c ; j++)
	{
		marked[i][j] = false;
		dis[i][j] = inf;
	}
	dis[Ps][Qs] = 0;
	priority_queue <pair<int , pair<int , int>> , vector <pair<int , pair<int , int>>> , greater<pair<int , pair<int , int>>>> pq;
	pq.push({Ps , {0 , Qs}});
	while(!pq.empty())
	{
		auto now = pq.top();  pq.pop();
		int D = now.S.F , p = now.F , q = now.S.S;
		if(marked[p][q])
			continue;
		marked[p][q] = true;
		if(q + 1 < c && D + h[p][q] < dis[p][q + 1])
		{
			dis[p][q + 1] = D + h[p][q];
			pq.push({p , {dis[p][q + 1] , q + 1}});
		}
		if(q - 1 >= 0 && D + h[p][q - 1] < dis[p][q - 1])
		{
			dis[p][q - 1] = D + h[p][q - 1];
			pq.push({p , {dis[p][q - 1] , q - 1}});
		}
		if(p + 1 <= R && D + v[p][q] < dis[p + 1][q])
		{
			dis[p + 1][q] = D + v[p][q];
			pq.push({p + 1 , {dis[p + 1][q] , q}});
		}
	}
	for(int i = 0 ; i < c ; i++)
	{
		//cout << Ps << " " << Qs << " " << R << " " << i << " : " << dis[R][i] << endl;
		nex[num][Qs][i] = dis[R][i];
	}
	if(num == 0)
	{
		for(int i = 0 ; i < c ; i++)
			adj[Qs][i] = dis[Ps][i];
	}
}
 
void Solve(int Qs)
{
	for(int i = 0 ; i < las + 2 ; i++)  for(int j = 0 ; j < c ; j++)
	{
		dis2[i][j] = inf;
	}
	for(int i = 0 ; i < c ; i++)
		dis2[0][i] = adj[Qs][i];
	for(int i = 0 ; i <= las ; i++)
	{
		for(int j = 0 ; j < c ; j++)  for(int k = 0 ; k < c ; k++)
		{
			dis2[i + 1][k] = min(dis2[i + 1][k] , dis2[i][j] + nex[i][j][k]);
			//cout << i << " " << j << " " << k << " " << dis2[i][j] << " " << nex[i][j][k] << endl;
		}
	}
	for(int i = 0 ; i < c ; i++)
	{
		//cout << Qs << " " << i << " : " << dis2[las + 1][i] << endl;
		ans[Qs][i] = dis2[las + 1][i];
	}
}
 
void init(int R , int C , int H[5000][200] , int V[5000][200])
{
	r = R;  c = C;
	for(int i = 0 ; i < R ; i++)  for(int j = 0 ; j + 1 < C ; j++)
		h[i][j] = H[i][j];
	for(int i = 0 ; i + 1 < R ; i++)  for(int j = 0 ; j < C ; j++)
		v[i][j] = V[i][j];
	for(int i = 0 ; i < R ; i += Sq)  for(int j = 0 ; j < C ; j++)
		Dij(i / Sq , j);
}
 
void changeH(int P , int Q , int W)
{
	is_update = false;
	h[P][Q] = W;
	for(int j = 0 ; j < c ; j++)
	{
		Dij(P / Sq , j);
		if(P > 0 && P % Sq == 0)
			Dij((P - 1) / Sq , j);
	}
}
 
void changeV(int P , int Q , int W)
{
	is_update = false;
	v[P][Q] = W;
	for(int j = 0 ; j < c ; j++)
		Dij(P / Sq , j);
}
 
int escape(int v1 , int v2)
{
	if(!is_update)
	{
		for(int i = 0 ; i < c ; i++)
			Solve(i);
		is_update = true;
	}
	return ans[v1][v2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 42 ms 17236 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 5 ms 14720 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6676 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 52 ms 8604 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9388 ms 7116 KB Output is correct
2 Correct 6629 ms 7108 KB Output is correct
3 Correct 9161 ms 6996 KB Output is correct
4 Correct 9102 ms 7116 KB Output is correct
5 Correct 8598 ms 7120 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Execution timed out 20086 ms 6896 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 21848 KB Output is correct
2 Correct 17 ms 21596 KB Output is correct
3 Correct 17 ms 21668 KB Output is correct
4 Correct 35 ms 23128 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9263 ms 7120 KB Output is correct
2 Correct 6824 ms 7000 KB Output is correct
3 Correct 9015 ms 7028 KB Output is correct
4 Correct 9170 ms 6996 KB Output is correct
5 Correct 8900 ms 7120 KB Output is correct
6 Correct 15 ms 21852 KB Output is correct
7 Correct 27 ms 21828 KB Output is correct
8 Correct 16 ms 21852 KB Output is correct
9 Correct 33 ms 23164 KB Output is correct
10 Correct 4 ms 14684 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 35 ms 17608 KB Output is correct
13 Correct 5 ms 14684 KB Output is correct
14 Correct 4 ms 14684 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6716 KB Output is correct
21 Correct 1 ms 6588 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 39 ms 9036 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Execution timed out 20092 ms 7000 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8592 ms 7116 KB Output is correct
2 Correct 6849 ms 7108 KB Output is correct
3 Correct 9067 ms 7112 KB Output is correct
4 Correct 8915 ms 7120 KB Output is correct
5 Correct 8545 ms 7112 KB Output is correct
6 Correct 14 ms 21852 KB Output is correct
7 Correct 16 ms 21624 KB Output is correct
8 Correct 17 ms 21852 KB Output is correct
9 Correct 32 ms 23076 KB Output is correct
10 Correct 5 ms 14684 KB Output is correct
11 Correct 5 ms 14832 KB Output is correct
12 Correct 36 ms 17488 KB Output is correct
13 Correct 5 ms 14680 KB Output is correct
14 Correct 7 ms 14680 KB Output is correct
15 Correct 12481 ms 35760 KB Output is correct
16 Execution timed out 20023 ms 33472 KB Time limit exceeded
17 Halted 0 ms 0 KB -