Submission #876922

#	Time	Username	Problem	Language	Result	Execution time	Memory
876922		ReLice	Soccer (JOI17_soccer)	C++17	100 / 100	276 ms	26436 KiB

soccer

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define ins insert
#define bc back()
#define str string
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9;
const ll N=5e2+7;
const ld eps=1e-9;
struct node{
	ll x,y,tp,d;
	bool operator <(const node &b)const{
		return d>b.d;
	}
};
ll d[N][N][5];
priority_queue<node> pq;
ll xd[4]={-1,1,0,0},yd[4]={0,0,-1,1};
ll l,w,n,a,b,c,x,y;
bool ok(ll x,ll y){
	return x<=l && x>=0 && y<=w && y>=0;
}
void inq(ll x,ll y,ll tp,ll dd){
	if(!ok(x,y))return;
	if(d[x][y][tp]>dd){
		d[x][y][tp]=dd;
		pq.push({x,y,tp,dd});
	}
}
void solve(){
	ll i,j;
    cin>>l>>w>>a>>b>>c>>n;
    ll dis[l+1][w+1];
    queue<pair<ll,ll>> q;
    vector<pair<ll,ll>> v;
    memset(dis,0x3f,sizeof(dis));
    for(i=0;i<n;i++){
		cin>>x>>y;
		v.pb({x,y});
		dis[x][y]=0;
		q.push({x,y});
	}
    while(q.sz){
		ll x=q.front().fr,y=q.front().sc;
		q.pop();
		for(i=0;i<4;i++){
			if(!ok(x+xd[i],y+yd[i])) continue;
			if(dis[x+xd[i]][y+yd[i]]>dis[x][y]+1){
				dis[x+xd[i]][y+yd[i]]=dis[x][y]+1;
				q.push({x+xd[i],y+yd[i]});
			}
		}
	}
	memset(d,0x3f,sizeof(d));
	pq.push({v[0].fr,v[0].sc,4,0});
	d[v[0].fr][v[0].sc][4]=0;
	b+=a;
	while(pq.sz){
		node x=pq.top();
		pq.pop();
		if(x.d!=d[x.x][x.y][x.tp])continue;
		if(x.tp==4){
			for(i=0;i<4;i++){
				inq(x.x+xd[i],x.y+yd[i],4ll,x.d+c);
				inq(x.x+xd[i],x.y+yd[i],i,x.d+b);
			}
		}else{
			inq(x.x+xd[x.tp],x.y+yd[x.tp],x.tp,x.d+a);
			inq(x.x,x.y,4ll,x.d+c*dis[x.x][x.y]);
		}
	}
	cout<<d[v.bc.fr][v.bc.sc][4]<<endl;
}

signed main(){
    start();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*









*/

Compilation message (stderr)

soccer.cpp: In function 'void solve()':
soccer.cpp:50:7: warning: unused variable 'j' [-Wunused-variable]
   50 |  ll i,j;
      |       ^

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