Submission #134471

#	Time	Username	Problem	Language	Result	Execution time	Memory
134471		model_code	Virus Experiment (JOI19_virus)	C++17	100 / 100	838 ms	120684 KiB

virus

#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 (stderr)

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 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80