Submission #670570

#	Time	Username	Problem	Language	Result	Execution time	Memory
670570		S2speed	Soccer (JOI17_soccer)	C++17	0 / 100	249 ms	262144 KiB

soccer

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<pll , ll> plll;
typedef pair<ll , plll> pllll;

const ll maxn = 502 , inf = 2e18;

ll n , m , A , B , C;
ll dis[maxn][maxn][5];
short int f[maxn][maxn];
vector<pll> bfs;
priority_queue<pllll , vector<pllll> , greater<pllll>> pq;

void BFS(){
	ll x = 0;
	while(x < sze(bfs)){
		ll i = bfs[x].first , j = bfs[x++].second;
		if(i > 0){
			if(f[i - 1][j] > f[i][j]){
				f[i - 1][j] = f[i][j] + 1;
				bfs.push_back({i - 1 , j});
			}
		}
		if(j > 0){
			if(f[i][j - 1] > f[i][j]){
				f[i][j - 1] = f[i][j] + 1;
				bfs.push_back({i , j - 1});
			}
		}
		if(i < n){
			if(f[i + 1][j] > f[i][j]){
				f[i + 1][j] = f[i][j] + 1;
				bfs.push_back({i + 1 , j});
			}
		}
		if(j < m){
			if(f[i][j + 1] > f[i][j]){
				f[i][j + 1] = f[i][j] + 1;
				bfs.push_back({i , j + 1});
			}
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(f , 63 , sizeof(f));
	memset(dis , 63 , sizeof(dis));
	ll k , x , y;
	cin>>n>>m>>A>>B>>C>>k;
	for(ll i = 0 ; i < k ; i++){
		cin>>x>>y;
		if(i == 0){
			dis[x][y][0] = 0;
			pq.push({0 , {{x , y} , 0}});
		}
		if(f[x][y] > 0) bfs.push_back({x , y});
		f[x][y] = 0;
	}
	BFS();
//	while(!pq.empty()){
//		pllll p = pq.top(); pq.pop();
//		ll i = p.second.first.first , j = p.second.first.second , t = p.second.second;
//		if(dis[i][j][t] != p.first) continue;
//		if(t == 0){
//			ll ps = dis[i][j][0] + B;
//			if(dis[i][j][1] > ps){
//				dis[i][j][1] = ps;
//				pq.push({ps , {{i , j} , 1}});
//			}
//			if(dis[i][j][2] > ps){
//				dis[i][j][2] = ps;
//				pq.push({ps , {{i , j} , 2}});
//			}
//			if(dis[i][j][3] > ps){
//				dis[i][j][3] = ps;
//				pq.push({ps , {{i , j} , 3}});
//			}
//			if(dis[i][j][4] > ps){
//				dis[i][j][4] = ps;
//				pq.push({ps , {{i , j} , 4}});
//			}
//			ll dr = dis[i][j][0] + C;
//			if(i > 0){
//				if(dis[i - 1][j][0] > dr){
//					dis[i - 1][j][0] = dr;
//					pq.push({dr , {{i - 1 , j} , 0}});
//				}
//			}
//			if(j > 0){
//				if(dis[i][j - 1][0] > dr){
//					dis[i][j - 1][0] = dr;
//					pq.push({dr , {{i , j - 1} , 0}});
//				}
//			}
//			if(i < n){
//				if(dis[i + 1][j][0] > dr){
//					dis[i + 1][j][0] = dr;
//					pq.push({dr , {{i + 1 , j} , 0}});
//				}
//			}
//			if(j < m){
//				if(dis[i][j + 1][0] > dr){
//					dis[i][j + 1][0] = dr;
//					pq.push({dr , {{i , j + 1} , 0}});
//				}
//			}
//		} else {
//			ll rc = dis[i][j][t] + f[i][j] * C;
//			if(dis[i][j][0] > rc){
//				dis[i][j][0] = rc;
//				pq.push({rc , {{i , j} , 0}});
//			}
//		}
//		if(t == 1){
//			ll ps = dis[i][j][1] + A;
//			if(i > 0){
//				if(dis[i - 1][j][1] > ps){
//					dis[i - 1][j][1] = ps;
//					pq.push({ps , {{i - 1 , j} , 1}});
//				}
//			}
//		} else if(t == 2){
//			ll ps = dis[i][j][2] + A;
//			if(i < n){
//				if(dis[i + 1][j][2] > ps){
//					dis[i + 1][j][2] = ps;
//					pq.push({ps , {{i + 1 , j} , 2}});
//				}
//			}
//		} else if(t == 3){
//			ll ps = dis[i][j][3] + A;
//			if(j > 0){
//				if(dis[i][j - 1][3] > ps){
//					dis[i][j - 1][3] = ps;
//					pq.push({ps , {{i , j - 1} , 3}});
//				}
//			}
//		} else if(t == 4){
//			ll ps = dis[i][j][4] + A;
//			if(j < m){
//				if(dis[i][j + 1][4] > ps){
//					dis[i][j + 1][4] = ps;
//					pq.push({ps , {{i , j + 1} , 4}});
//				}
//			}
//		}
//	}
//	ll ans = inf;
//	for(ll j = 0 ; j < 5 ; j++) ans = min(ans , dis[x][y][j]);
//	cout<<ans<<'\n';
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65