oj.uz

Submission #448328

# Submission time Handle Problem Language Result Execution time Memory
448328 2021-07-29T17:57:30 Z koioi.org-koosaga Virus Experiment (JOI19_virus) C++17
100 / 100
 1180 ms 241784 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXV = 1300000;

struct disj{
	int pa[MAXV];
	void init(){
		iota(pa, pa + MAXV, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

int n, m;
int V;
bool good[MAXV][16];
int pa[MAXV], nxt[MAXV], sz[MAXV];
unordered_map<int, char> nei[MAXV / 2];
vector<int> justVisit[MAXV / 2];
int idx[MAXV];

int find(int x){
	return pa[x] = (pa[x] == x ? x : find(pa[x]));
}

int find_next(int x){
	while(sz(justVisit[idx[x]]) && find(justVisit[idx[x]].back()) == x){
		justVisit[idx[x]].pop_back();
	}
	if(sz(justVisit[idx[x]]) == 0) return x;
	return justVisit[idx[x]].back();
}

void merge_to(int u, int v){
	u = find(u);
	if(u == v) return;
	pa[u] = v;
	int iu = idx[u], iv = idx[v];
	if(sz[u] > sz[v]) swap(iu, iv);
	sz[v] += sz[u];
	idx[v] = iv;
	if(iu >= MAXV / 2 || iv >= MAXV / 2) return;
	{
		for(auto &i : justVisit[iu]) justVisit[iv].push_back(i);
	}
	{
		vector<int> toKill;
		for(auto &[x, y] : nei[iu]){
			if(nei[iv].find(x) == nei[iv].end()){
				nei[iv][x] = y;
				continue;
			}
			else{
				nei[iv][x] |= y;
				if(good[x][nei[iv][x]]){
					toKill.push_back(x);
				}
			}
		}
		for(auto &x : toKill){
			nei[iv].erase(x);
			justVisit[iv].push_back(x);
		}
	}
	justVisit[iu].clear();
	justVisit[iu].shrink_to_fit();
	nei[iu].clear();
}

void solve(){
	disj.init();
	iota(pa, pa + MAXV, 0);
	fill(sz, sz + V, 1);
	iota(idx, idx + MAXV, 0);
	for(int i = 0; i < V; i++){
		nxt[i] = find_next(i);
	}
	int curV = V;
	for(int i = 0; i < V; i++){
		if(find(i) != i) continue;
		if(i == find(nxt[i])) continue;
		if(!disj.uni(i, nxt[i])){
			for(int j = find(nxt[i]); find(j) != find(V); j = find(nxt[j])){
				merge_to(j, V);
			}
			disj.uni(i, V);
			nxt[V] = find_next(V);
			V++;
		}
	}
	int dap = 1e9;
	int cnt = 0;
	for(int i = 0; i < curV; i++){
		int r = find(i);
		if(find(r) == find(nxt[r])){
			if(dap > sz[r]){
				dap = sz[r];
				cnt = 0;
			}
			if(dap == sz[r]) cnt++;
		}
	}
	printf("%d\n%d\n", dap, cnt);
}

const int MAXN = 808;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
char buf[200005];
int mp[256];

int main(){
	int idx[MAXN][MAXN] = {};
	int dead[MAXN][MAXN] = {};

	mp['N'] = 0;
	mp['W'] = 1;
	mp['S'] = 2;
	mp['E'] = 3;
	int k;
	scanf("%d %d %d",&k,&n,&m);
	scanf("%s", buf);
	for(int i=0; i<k; i++){
		buf[i + k] = buf[i];
	}
	k <<= 1;
	int maxt[16] = {};
	for(int i=0; i<16; i++){
		int cnt = 0;
		for(int j=0; j<k; j++){
			if((i >> mp[buf[j]]) & 1){
				cnt++;
				maxt[i] = max(maxt[i], cnt);
			}
			else{
				cnt = 0;
			}
		}
		if(maxt[i] == k) maxt[i] = 1e9;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int x; scanf("%d",&x);
			if(x == 0){
				dead[i][j] = 1;
				continue;
			}
			idx[i][j] = V;
			for(int k=0; k<16; k++){
				if(x <= maxt[k]) good[V][k] = 1;
			}
			V++;
		}
	}
	auto ok = [&](int x, int y){
		return x >= 0 && x < n && y >= 0 && y < m && !dead[x][y];
	};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(!ok(i, j)) continue;
			for(int k = 0; k < 4; k++){
				if(ok(i + dx[k], j + dy[k])){
					pi v(idx[i + dx[k]][j + dy[k]], 1 << k);
					if(good[v.first][v.second]) justVisit[idx[i][j]].push_back(v.first);
					else nei[idx[i][j]].insert(v);
				}
			}
		}
	}
	solve();
}

Compilation message

virus.cpp: In function 'void merge_to(int, int)':
virus.cpp:66:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |     if(good[x][nei[iv][x]]){
      |                          ^
virus.cpp: In function 'int main()':
virus.cpp:142:21: warning: array subscript has type 'char' [-Wchar-subscripts]
  142 |    if((i >> mp[buf[j]]) & 1){
      |                ~~~~~^
virus.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  scanf("%d %d %d",&k,&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |  scanf("%s", buf);
      |  ~~~~~^~~~~~~~~~~
virus.cpp:154:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |    int x; scanf("%d",&x);
      |           ~~~~~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 71748 KB Output is correct
2 Correct 614 ms 235972 KB Output is correct
3 Correct 540 ms 236652 KB Output is correct
4 Correct 525 ms 236740 KB Output is correct
5 Correct 514 ms 236872 KB Output is correct
6 Correct 39 ms 71560 KB Output is correct
7 Correct 1180 ms 241784 KB Output is correct
8 Correct 215 ms 129216 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 71496 KB Output is correct
2 Correct 44 ms 71760 KB Output is correct
3 Correct 56 ms 71748 KB Output is correct
4 Correct 43 ms 71688 KB Output is correct
5 Correct 56 ms 71648 KB Output is correct
6 Correct 57 ms 72004 KB Output is correct
7 Correct 40 ms 71452 KB Output is correct
8 Correct 55 ms 71748 KB Output is correct
9 Correct 42 ms 71860 KB Output is correct
10 Correct 43 ms 71696 KB Output is correct
11 Correct 49 ms 72252 KB Output is correct
12 Correct 49 ms 71864 KB Output is correct
13 Correct 55 ms 72224 KB Output is correct
14 Correct 56 ms 72240 KB Output is correct
15 Correct 58 ms 72228 KB Output is correct
16 Correct 58 ms 72176 KB Output is correct
17 Correct 51 ms 72132 KB Output is correct
18 Correct 49 ms 72032 KB Output is correct
19 Correct 57 ms 72288 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 71748 KB Output is correct
2 Correct 614 ms 235972 KB Output is correct
3 Correct 540 ms 236652 KB Output is correct
4 Correct 525 ms 236740 KB Output is correct
5 Correct 514 ms 236872 KB Output is correct
6 Correct 39 ms 71560 KB Output is correct
7 Correct 1180 ms 241784 KB Output is correct
8 Correct 215 ms 129216 KB Output is correct
9 Correct 40 ms 71496 KB Output is correct
10 Correct 44 ms 71760 KB Output is correct
11 Correct 56 ms 71748 KB Output is correct
12 Correct 43 ms 71688 KB Output is correct
13 Correct 56 ms 71648 KB Output is correct
14 Correct 57 ms 72004 KB Output is correct
15 Correct 40 ms 71452 KB Output is correct
16 Correct 55 ms 71748 KB Output is correct
17 Correct 42 ms 71860 KB Output is correct
18 Correct 43 ms 71696 KB Output is correct
19 Correct 49 ms 72252 KB Output is correct
20 Correct 49 ms 71864 KB Output is correct
21 Correct 55 ms 72224 KB Output is correct
22 Correct 56 ms 72240 KB Output is correct
23 Correct 58 ms 72228 KB Output is correct
24 Correct 58 ms 72176 KB Output is correct
25 Correct 51 ms 72132 KB Output is correct
26 Correct 49 ms 72032 KB Output is correct
27 Correct 57 ms 72288 KB Output is correct
28 Correct 568 ms 140344 KB Output is correct
29 Correct 393 ms 144680 KB Output is correct
30 Correct 953 ms 219812 KB Output is correct
31 Correct 723 ms 178228 KB Output is correct
32 Correct 783 ms 181124 KB Output is correct
33 Correct 578 ms 233904 KB Output is correct
34 Correct 642 ms 135396 KB Output is correct
35 Correct 402 ms 116676 KB Output is correct
36 Correct 1031 ms 179856 KB Output is correct
37 Correct 631 ms 145476 KB Output is correct
38 Correct 407 ms 118464 KB Output is correct
39 Correct 745 ms 220952 KB Output is correct
40 Correct 888 ms 216236 KB Output is correct
41 Correct 518 ms 216724 KB Output is correct
42 Correct 385 ms 103840 KB Output is correct
43 Correct 563 ms 205828 KB Output is correct
44 Correct 222 ms 129276 KB Output is correct