oj.uz

Submission #590368

# Submission time Handle Problem Language Result Execution time Memory
590368 2022-07-05T21:37:45 Z Gilwall Soccer (JOI17_soccer) C++14
0 / 100
 3000 ms 21072 KB 
#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;


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));
			}
		}
	}
	////
	int SZ = V;
    bool vis[SZ];
    int d[SZ];
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	M00(i, SZ) d[i] = 1e14;
	int s = players[0].f * W + players[0].s;
	int t = players[N-1].f * W + players[N-1].s;
	d[s] = 0;
	pq.push(mp(0, s));
	while(!pq.empty()) {
		pi t = pq.top(); pq.pop();
		if(vis[t.s]) continue;
		vis[t.s] = 1;

		int x = t.s/W;
		int y = t.s%W;
		int v = t.s;
		
		vector<pi> edges;
		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]);
				edges.pb(mp(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]);
				edges.pb(mp(w, cost));
			}
		}
		for(auto v: edges) {
			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));
			}
		}
	}
	cout << d[t] << endl;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 7132 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Execution timed out 3073 ms 12932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3037 ms 21072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 7132 KB Output is correct
2 Correct 2 ms 2516 KB Output is correct
3 Execution timed out 3073 ms 12932 KB Time limit exceeded
4 Halted 0 ms 0 KB -