Submission #590361

#	Time	Username	Problem	Language	Result	Execution time	Memory
590361		Gilwall	Soccer (JOI17_soccer)	C++14	0 / 100	263 ms	262144 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))

#define MOO(i,a,b) for (int i=a; i<b; i++)
#define M00(i,a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)

#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _<< " _ " <<

#define int long long

typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;

typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;

const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 1e9+7;

int POW(int b, int e) {
	int r = 1;
	while(e) {
		if(e % 2 == 1) {
			r *= b;
			r %= MOD;
		}
		e /= 2;
		b *= b;
		b %= MOD;
	}
	return r;
}
int gcd(int a, int b) {
	if(b > a) return gcd(b,a);
	if(b == 0) return a;
	return gcd(b, a % b);
}
int INV(int a) {
	return POW(a, MOD-2);
}
//Constants and Variables here
int H, W;	
int A,B,C;
int N;

template<int SZ> struct dijkstra {
    const int inf = 1e15;
    vector<pi> adj[SZ];
    bool vis[SZ];
    int d[SZ];

    void addEdge(int u, int v, int l) {
        adj[u].pb(mp(v, l));
    }
    int dist(int v) {
        return d[v];
    }
    void build(int u) {
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        M00(i, SZ) d[i] = inf;
        d[u] = 0;
        pq.push(mp(0, u));
        while(!pq.empty()) {
            pi t = pq.top(); pq.pop();
            if(vis[t.s]) continue;
            vis[t.s] = 1;

            for(auto v: adj[t.s]) {
                if(d[v.f] > d[t.s] + v.s) {
                    d[v.f] = d[t.s] + v.s;
                    pq.push(mp(d[t.s]+v.s, v.f));
                }
            }
        }
    }
};

const int V = 501*501;
vi dx = {0,0,1,-1};
vi dy = {1,-1,0,0};

int32_t main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> H >> W >> A >> B >> C >> N;
	H++; W++;
	vector<vi> arr(H, vi(W, -1));
	queue<pair<pi, int>> Q;
	vector<pi> players;
	M00(i, N) {
		int x, y;
		cin >> x >> y;
		players.pb(mp(x,y));
		if(arr[x][y] < 0) {
			arr[x][y] = 0;
			Q.push(mp(mp(x,y),0));
		}
	}
	while(Q.size() > 0) {
		auto A = Q.front();
		Q.pop();
		int x = A.f.f, y = A.f.s;
		int d = A.s;
		M00(i, 4) {
			int xx = x + dx[i], yy = y + dy[i];
			if(0 <= xx && xx < H && 0 <= yy && yy <= W && arr[xx][yy] < 0) {
				arr[xx][yy] = d + 1;
				Q.push(mp(mp(xx,yy),d+1));
			}
		}
	}
	dijkstra<V> G;
	M00(x, H) M00(y, W) {
		//hash (x,y) -> x * W + y
		int v = x*W + y;
		M00(k, H) {
			int w = k*W + y;
			if(w != v) {
				int cost = min(abs(k-x) * C, A * abs(k-x) + B + C*arr[k][y]);
				G.addEdge(v, w, cost);
			}
		}
		M00(k, W) {
			int w = x*W + k;
			if(w != v) {
				int cost = min(abs(k-y) * C, A * abs(k-y) + B + C*arr[x][k]);
				G.addEdge(v, w, cost);
			}
		}
	}
	int s = players[0].f * W + players[0].s;
	int t = players[N-1].f * W + players[N-1].s;
	G.build(s);
	cout << G.dist(t) << endl;
}

Compilation message (stderr)

soccer.cpp:29:9: warning: ISO C++11 requires whitespace after the macro name
   29 | #define _<< " _ " <<
      |         ^

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