oj.uz

Submission #134471

# Submission time Handle Problem Language Result Execution time Memory
134471 2019-07-22T18:12:26 Z model_code Virus Experiment (JOI19_virus) C++17
100 / 100
 838 ms 120684 KB 
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> P;

char dir[4] = { 'E' , 'N' , 'W' , 'S' };
int di[4][2] = { {0,1},{-1,0},{0,-1},{1,0} };

#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)

const int MAX_V = 800*800+10;
struct Graph{
	int V;
	vector<int> G[MAX_V];
	vector<int> rG[MAX_V];
	
	void init(int V_){
		V = V_;
		for(int i = 0 ; i < V_ ; i ++){
			G[i].clear();
			rG[i].clear();
		}
	}
	
	void add_edge(int from,int to){
		G[from].push_back(to);
		rG[to].push_back(from);
	}
	
	int cmp[MAX_V];
	vector<int> vs;
	bool used[MAX_V];
	void dfs(int v){
		used[v] = true;
		for(int i = 0 ; i < G[v].size() ; i ++){
			if(!used[G[v][i]])dfs(G[v][i]);
		}
		vs.push_back(v);
	}
	void rdfs(int v,int k){
		used[v] = true;
		cmp[v] = k;
		for(int i = 0 ; i < rG[v].size() ; i ++){
			if(!used[rG[v][i]])rdfs(rG[v][i],k);
		}
	}
	int scc(){
		for(int i = 0 ; i < V ; i ++){
			used[i] = false;
		}
		vs.clear();
		for(int i = 0 ; i < V ; i ++){
			if(!used[i])dfs(i);
		}
		for(int i = 0 ; i < V ; i ++){
			used[i] = false;
		}
		int k = 0;
		for(int i = (int)vs.size()-1 ; i >= 0 ; --i){
			if(!used[vs[i]])rdfs(vs[i],k++);
		}
		return k;
	}
	
	int end[MAX_V];
	int end_cmp(int v){
		if(end[v] != -1)return end[v];
		for(int i = 0 ; i < G[v].size() ; i ++){
			if(cmp[G[v][i]] != cmp[v])return end[v] = end_cmp(G[v][i]);
		}
		return end[v] = cmp[v];
	}
}G;

int main(){
	static int n,r,c;
	static string d;
	static int u[802][802];
	scanf("%d%d%d",&n,&r,&c);
	cin >> d;
	for(int i = 1 ; i <= r ; i ++){
		for(int j = 1 ; j <= c ; j ++){
			scanf("%d",&u[i][j]);
			if(u[i][j] == 0)u[i][j] = 100001;
		}
	}
	
	int v[1<<4] = {};
	for(int i = 0 ; i < (1<<4) ; i ++){
		static bool b[100010];
		int cnt = 0;
		for(int j = 0 ; j < d.size() ; j ++){
			b[j] = false;
			for(int k = 0 ; k < 4 ; k ++){
				b[j] |= d[j] == dir[k] && ((i>>k)&1);
			}
			if(b[j])cnt ++;
			else cnt = 0;
			v[i] = max( v[i] , cnt );
		}
		if(cnt != d.size() && b[0] && b[d.size()-1]){
			cnt = 0;
			for(int i = 0 ; b[i] ; i ++)cnt ++;
			for(int i = d.size()-1 ; b[i] ; i --)cnt ++;
			v[i] = max( v[i] , cnt );
		}
		if(v[i] == d.size())v[i] = 100000;
	}
	
	static vector<P> cand;
	static int a[802][802] = {};
	static P rel[MAX_V] = {};
	static P rel_[MAX_V] = {};
	for(int i = 1 ; i <= r ; i ++){
		for(int j = 1 ; j <= c ; j ++){
			a[i][j] = (i-1)*c+j;
			rel[(i-1)*c+j] = P(i,j);
		}
	}
	static int k = r*c;
	static int num[MAX_V];
	static int ler[MAX_V];
	static int nn[MAX_V];
	while(k >= 1){
		G.init(k+1);
		for(int i = 1 ; i <= r ; i ++){
			for(int j = 1 ; j <= c ; j ++){
				for(int s = 0 ; s < 4 ; ++s){
					int id = a[i+di[s][0]][j+di[s][1]];
					if(id <= 0 || id == abs(a[i][j]))continue;
					int x = 0;
					for(int t = 0 ; t < 4 ; ++t){
						if(a[i+di[t][0]][j+di[t][1]] == id){
							x += 1<<t;
						}
					}
					if(v[x] >= u[i][j]){
						G.add_edge(id,abs(a[i][j]));
					}
				}
			}
		}
		for(int i = 1 ; i <= k ; i ++){
			if(G.G[i].size() == 0){
				cand.push_back(rel[i]);
				G.add_edge(i,0);
			}
		}
		
		int k_ = G.scc();
		for(int i = 0 ; i <= k ; i ++){
			G.end[i] = -1;
		}
		
		/*for(int i = 0 ; i <= k ; i ++){
			cout << G.cmp[i] << ":" << G.end_cmp(i) << endl;
		}*/
		
		int cnt = 0;
		vector<int> endcmp;
		for(int i = 1 ; i <= k ; i ++){
			if(G.cmp[i] == G.end_cmp(i)){
				endcmp.push_back(G.cmp[i]);
			}
		}
		sort(endcmp.begin(),endcmp.end());
		endcmp.erase(unique(endcmp.begin(),endcmp.end()),endcmp.end());
		cnt = endcmp.size();
		nn[G.cmp[0]] = 0;
		for(int i = 0 ; i < cnt ; i ++){
			nn[endcmp[i]] = i+1;
		}
		for(int i = 0 ; i <= k ; i ++){
			if(G.cmp[i] == G.end_cmp(i)){
				num[i] = nn[G.cmp[i]];
				ler[num[i]] = i;
			}
		}
		for(int i = 0 ; i <= k ; i ++){
			if(G.cmp[i] != G.end_cmp(i)){
				num[i] = -nn[G.end_cmp(i)];
			}
		}
		k = cnt;
		for(int i = 1 ; i <= k ; i ++){
			rel_[i] = rel[ler[i]];
		}
		for(int i = 1 ; i <= k ; i ++){
			rel[i] = rel_[i];
		}
		for(int i = 1 ; i <= r ; i ++){
			for(int j = 1 ; j <= c ; j ++){
				if(a[i][j] < 0)a[i][j] = -abs(num[-a[i][j]]);
				else a[i][j] = num[a[i][j]];
			}
		}
		
		queue<P> que;
		for(int i = 1 ; i <= r ; i ++){
			for(int j = 1 ; j <= c ; j ++){
				que.push(P(i,j));
			}
		}
		while(!que.empty()){
			P p = que.front(); que.pop();
			int i = p.first;
			int j = p.second;
			if(a[i][j] >= 0)continue;
			if(i == 0 || i == r+1 || j == 0 || j == c+1)continue;
			int s = 0;
			rep(k,4)if(a[i+di[k][0]][j+di[k][1]] == -a[i][j])s += 1<<k;
			if(v[s] >= u[i][j]){
				a[i][j] = -a[i][j];
				rep(k,4)que.push(P(i+di[k][0],j+di[k][1]));
			}
		}
	}
	
	static int ret = r*c;
	static int ret_cnt = 0;
	static bool used[802][802];
	rep(i,802)rep(j,802)used[i][j] = false;
	for(int i = 0 ; i < cand.size() ; i ++){
		int x = cand[i].first;
		int y = cand[i].second;
		if(u[x][y] == 100001)continue;
		vector<P> vec;
		queue<P> que;
		rep(k,4){
			que.push(P(x+di[k][0],y+di[k][1]));
		}
		used[x][y] = true;
		vec.push_back(P(x,y));
		while(!que.empty()){
			P p = que.front(); que.pop();
			int i = p.first;
			int j = p.second;
			if(i == 0 || i == r+1 || j == 0 || j == c+1 || used[i][j])continue;
			int s = 0;
			rep(k,4)if(used[i+di[k][0]][j+di[k][1]])s += 1<<k;
			if(v[s] >= u[i][j]){
				used[i][j] = true;
				vec.push_back(p);
				rep(k,4)que.push(P(i+di[k][0],j+di[k][1]));
			}
		}
		for(int i = 0 ; i < vec.size() ; i ++){
			used[vec[i].first][vec[i].second] = false;
		}
		if(vec.size() < ret){
			ret = vec.size();
			ret_cnt = 1;
		}
		else if(vec.size() == ret){
			ret_cnt ++;
		}
	}
	cout << ret << endl << ret_cnt*ret << endl;
}

Compilation message

virus.cpp: In member function 'void Graph::dfs(int)':
virus.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < G[v].size() ; i ++){
                   ~~^~~~~~~~~~~~~
virus.cpp: In member function 'void Graph::rdfs(int, int)':
virus.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < rG[v].size() ; i ++){
                   ~~^~~~~~~~~~~~~~
virus.cpp: In member function 'int Graph::end_cmp(int)':
virus.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < G[v].size() ; i ++){
                   ~~^~~~~~~~~~~~~
virus.cpp: In function 'int main()':
virus.cpp:98:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < d.size() ; j ++){
                   ~~^~~~~~~~~~
virus.cpp:107:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnt != d.size() && b[0] && b[d.size()-1]){
      ~~~~^~~~~~~~~~~
virus.cpp:113:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v[i] == d.size())v[i] = 100000;
      ~~~~~^~~~~~~~~~~
virus.cpp:156:7: warning: unused variable 'k_' [-Wunused-variable]
   int k_ = G.scc();
       ^~
virus.cpp:229:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < cand.size() ; i ++){
                  ~~^~~~~~~~~~~~~
virus.cpp:253:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < vec.size() ; i ++){
                   ~~^~~~~~~~~~~~
virus.cpp:256:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vec.size() < ret){
      ~~~~~~~~~~~^~~~~
virus.cpp:260:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(vec.size() == ret){
           ~~~~~~~~~~~^~~~~~
virus.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&r,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~
virus.cpp:89:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&u[i][j]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 31352 KB Output is correct
2 Correct 382 ms 94176 KB Output is correct
3 Correct 310 ms 96408 KB Output is correct
4 Correct 277 ms 96556 KB Output is correct
5 Correct 394 ms 84688 KB Output is correct
6 Correct 42 ms 36088 KB Output is correct
7 Correct 561 ms 99160 KB Output is correct
8 Correct 189 ms 53484 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31096 KB Output is correct
2 Correct 43 ms 31480 KB Output is correct
3 Correct 60 ms 31480 KB Output is correct
4 Correct 44 ms 31436 KB Output is correct
5 Correct 58 ms 31352 KB Output is correct
6 Correct 61 ms 31864 KB Output is correct
7 Correct 30 ms 31228 KB Output is correct
8 Correct 59 ms 31832 KB Output is correct
9 Correct 32 ms 31608 KB Output is correct
10 Correct 44 ms 31480 KB Output is correct
11 Correct 31 ms 31608 KB Output is correct
12 Correct 33 ms 31608 KB Output is correct
13 Correct 59 ms 31864 KB Output is correct
14 Correct 59 ms 31864 KB Output is correct
15 Correct 59 ms 31864 KB Output is correct
16 Correct 63 ms 31844 KB Output is correct
17 Correct 46 ms 31736 KB Output is correct
18 Correct 33 ms 31608 KB Output is correct
19 Correct 60 ms 31736 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 31352 KB Output is correct
2 Correct 382 ms 94176 KB Output is correct
3 Correct 310 ms 96408 KB Output is correct
4 Correct 277 ms 96556 KB Output is correct
5 Correct 394 ms 84688 KB Output is correct
6 Correct 42 ms 36088 KB Output is correct
7 Correct 561 ms 99160 KB Output is correct
8 Correct 189 ms 53484 KB Output is correct
9 Correct 30 ms 31096 KB Output is correct
10 Correct 43 ms 31480 KB Output is correct
11 Correct 60 ms 31480 KB Output is correct
12 Correct 44 ms 31436 KB Output is correct
13 Correct 58 ms 31352 KB Output is correct
14 Correct 61 ms 31864 KB Output is correct
15 Correct 30 ms 31228 KB Output is correct
16 Correct 59 ms 31832 KB Output is correct
17 Correct 32 ms 31608 KB Output is correct
18 Correct 44 ms 31480 KB Output is correct
19 Correct 31 ms 31608 KB Output is correct
20 Correct 33 ms 31608 KB Output is correct
21 Correct 59 ms 31864 KB Output is correct
22 Correct 59 ms 31864 KB Output is correct
23 Correct 59 ms 31864 KB Output is correct
24 Correct 63 ms 31844 KB Output is correct
25 Correct 46 ms 31736 KB Output is correct
26 Correct 33 ms 31608 KB Output is correct
27 Correct 60 ms 31736 KB Output is correct
28 Correct 674 ms 119584 KB Output is correct
29 Correct 671 ms 114396 KB Output is correct
30 Correct 610 ms 114308 KB Output is correct
31 Correct 516 ms 90968 KB Output is correct
32 Correct 493 ms 92544 KB Output is correct
33 Correct 354 ms 92152 KB Output is correct
34 Correct 838 ms 106508 KB Output is correct
35 Correct 581 ms 91152 KB Output is correct
36 Correct 708 ms 94432 KB Output is correct
37 Correct 667 ms 101916 KB Output is correct
38 Correct 672 ms 120684 KB Output is correct
39 Correct 512 ms 89640 KB Output is correct
40 Correct 550 ms 89820 KB Output is correct
41 Correct 294 ms 95492 KB Output is correct
42 Correct 652 ms 98596 KB Output is correct
43 Correct 636 ms 97144 KB Output is correct
44 Correct 193 ms 53352 KB Output is correct