oj.uz

답안 #489654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489654 2021-11-23T14:29:01 Z fhvirus 바이러스 (JOI19_virus) C++17
100 / 100
 927 ms 18020 KB 
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif

const int INF = 8e7;
const int dc[4] = { 'N', 'S', 'W', 'E' };
const int dx[4] = {  -1,   1,   0,   0 };
const int dy[4] = {   0,   0,  -1,   1 };
[[ gnu::pure ]] int ctod(char c){
	for(int k = 0; k < 4; ++k){
		if(c == dc[k])
			return k;
	}
	return -1;
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// input
	int M, R, C;
	cin >> M >> R >> C;
	string D; cin >> D;
	vector<vector<int>> U(R, vector<int>(C));
	for(vector<int> &v: U)
		for(int &i: v) cin >> i;

	// preprocess D
	D += D;
	vector<int> pre(16, 0);
	vector<int> thr(16, 0);
	for(int i = 0; i < M*2; ++i){
		for(int j = 1; j < 16; ++j)
			if(j >> ctod(D[i]) & 1){
				++pre[j];
				chmax(thr[j], pre[j]);
			} else pre[j] = 0;
	}
	for(int j = 1; j < 16; ++j)
		if(thr[j] == M*2) thr[j] = INF;

	vector<pii> perm(R*C);
	for(int i = 0, k = 0; i < R; ++i)
		for(int j = 0; j < C; ++j, ++k)
			perm[k] = pii(i, j);
	shuffle(AI(perm), mt19937(random_device()()));

	int mnv = INF, mnc = 0;
	vector<vector<bool>> owr(R, vector<bool>(C, false));
	vector<vector<bool>> vis(R, vector<bool>(C, false));
	function<bool(int, int)> inside = [&](int r, int c){
		return (0 <= r and r < R and 0 <= c and c < C);
	};
	function<bool(int, int)> infect = [&](int r, int c){
		if(U[r][c] == 0) return false;
		int msk = 0;
		for(int x, y, d = 0; d < 4; ++d){
			x = r + dx[d]; y = c + dy[d];
			if(inside(x, y) and vis[x][y]) msk |= (1<<d);
		}
		return (thr[msk] >= U[r][c]);
	};

	int cnt = 0;
	vector<pii> tmp;
	queue<pii> q;
	for(auto [sx, sy]: perm){
		owr[sx][sy] = true;
		if(U[sx][sy] == 0) continue;

		vis[sx][sy] = true;
		cnt = 1;
		tmp.pb(sx, sy);
		q.emplace(sx, sy);
		
		while(!q.empty()){
			auto [r, c] = q.front(); q.pop();
			for(int x, y, d = 0; d < 4; ++d){
				x = r + dx[d]; y = c + dy[d];
				if(!inside(x, y)) continue;
				if(U[x][y] == 0 or vis[x][y]) continue;
				if(!infect(x, y)) continue;
				if(owr[x][y]){ cnt = -1; break; }
				vis[x][y] = true;
				++cnt;
				tmp.pb(x, y);
				q.emplace(x, y);
			}
			if(cnt == -1) break;
		}

		for(auto [r, c]: tmp)
			vis[r][c] = false;
		tmp.clear();

		if(cnt == -1) continue;
		if(chmin(mnv, cnt)) mnc = 0;
		if(mnv == cnt) mnc += cnt;
	}

	cout << mnv << '\n';
	cout << mnc << '\n';
	return 0;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 222 ms 9364 KB Output is correct
3 Correct 575 ms 8972 KB Output is correct
4 Correct 535 ms 8900 KB Output is correct
5 Correct 176 ms 8988 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 654 ms 9168 KB Output is correct
8 Correct 69 ms 4460 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 5 ms 716 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 9 ms 716 KB Output is correct
6 Correct 11 ms 764 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 6 ms 716 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 10 ms 844 KB Output is correct
14 Correct 10 ms 764 KB Output is correct
15 Correct 9 ms 716 KB Output is correct
16 Correct 9 ms 764 KB Output is correct
17 Correct 5 ms 460 KB Output is correct
18 Correct 2 ms 324 KB Output is correct
19 Correct 9 ms 844 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 222 ms 9364 KB Output is correct
3 Correct 575 ms 8972 KB Output is correct
4 Correct 535 ms 8900 KB Output is correct
5 Correct 176 ms 8988 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 654 ms 9168 KB Output is correct
8 Correct 69 ms 4460 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 5 ms 716 KB Output is correct
11 Correct 8 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 9 ms 716 KB Output is correct
14 Correct 11 ms 764 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 8 ms 716 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 6 ms 716 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 3 ms 332 KB Output is correct
21 Correct 10 ms 844 KB Output is correct
22 Correct 10 ms 764 KB Output is correct
23 Correct 9 ms 716 KB Output is correct
24 Correct 9 ms 764 KB Output is correct
25 Correct 5 ms 460 KB Output is correct
26 Correct 2 ms 324 KB Output is correct
27 Correct 9 ms 844 KB Output is correct
28 Correct 884 ms 17976 KB Output is correct
29 Correct 878 ms 17984 KB Output is correct
30 Correct 916 ms 18020 KB Output is correct
31 Correct 874 ms 13632 KB Output is correct
32 Correct 808 ms 11472 KB Output is correct
33 Correct 327 ms 9672 KB Output is correct
34 Correct 927 ms 17752 KB Output is correct
35 Correct 677 ms 11452 KB Output is correct
36 Correct 634 ms 9776 KB Output is correct
37 Correct 917 ms 11696 KB Output is correct
38 Correct 858 ms 17676 KB Output is correct
39 Correct 284 ms 10756 KB Output is correct
40 Correct 305 ms 10652 KB Output is correct
41 Correct 239 ms 9540 KB Output is correct
42 Correct 703 ms 13316 KB Output is correct
43 Correct 827 ms 13972 KB Output is correct
44 Correct 72 ms 4944 KB Output is correct