Submission #819110

#	Time	Username	Problem	Language	Result	Execution time	Memory
819110		fatemetmhr	Virus Experiment (JOI19_virus)	C++17	100 / 100	462 ms	207568 KiB

virus

//  ~ Be Name Khoda ~  //
 
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
 
using namespace std;
 
typedef long long ll;
 
#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
 
const int maxn  =  1e6   + 10;
const int maxn3 =  810;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;
 
/*
 
* 0 *
1 X 2
* 3 *
 
*/
 
char c[4] = {'N', 'W', 'E', 'S'};
pair <int, int> adj[4] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
int mx[100], mark[maxn], cmp[maxn3][maxn3];
int a[maxn3][maxn3], n, m;
vector <pair<int, int>> ed[maxn], eversaw[maxn], av[maxn];
bool Run = false;
 
bool ok(int i, int j){
	return min(i, j) >= 0 && i < n && j < m && a[i][j];
}
 
bool check_ed(int x, int y, int a){
    if(cmp[x][y] == a)
        return false;
    int mask = 0;
    for(int i = 0; i < 4; i++) 
        if(ok(x - adj[i].fi, y - adj[i].se) && cmp[x - adj[i].fi][y - adj[i].se] == a)
            mask += (1 << i);
    return mx[mask] >= (::a[x][y]);
}
 
int merge(int a, int b){
	if(a == b)
		return a;
    if(av[a].size() < av[b].size())
        swap(a, b);
    for(auto [u, v] : av[b]){
        av[a].pb({u, v});
        cmp[u][v] = a;
    }
    for(auto [u, v] : av[b]) for(int i = 0; i < 4; i++) 
        if(ok(u + adj[i].fi, v + adj[i].se) && check_ed(u + adj[i].fi, v + adj[i].se, a))
            ed[a].pb({u + adj[i].fi, v + adj[i].se});
    for(auto p : ed[b]){
    	//cout << "it's " << p.fi << ' ' << p.se << endl;
        ed[a].pb(p);
    }
    for(auto p : eversaw[b])
        eversaw[a].pb(p);
    av[b].clear();
    eversaw[b].clear();
    ed[b].clear();
    av[b].shrink_to_fit();
    eversaw[b].shrink_to_fit();
    ed[b].shrink_to_fit();
	//cout << "here merge of " << a << ' ' << b << endl;
    return a;
}
 
bool dfs(int v){
    mark[v] = 1;
    while(ed[v].size()){
        int u = cmp[ed[v].back().fi][ed[v].back().se];
        pair <int, int> tmp = ed[v].back();
        //cout << v << ' ' << u << ' ' << mark[u] << ' ' << ed[v].back().fi << ' ' << ed[v].back().se << endl;
        if(u == v){
        	ed[v].pop_back();
        	continue;
        }
        eversaw[v].pb(ed[v].back());
        ed[v].pop_back();
        if(!mark[u]){
            if(dfs(u)){
            	if(eversaw[v].empty())
            		exit(0);
                v = merge(cmp[tmp.fi][tmp.se], v);
            }
            mark[v] = 1;
        }
        else if(mark[u] == 1){
            ed[v].pb(tmp);
            //cout << ed[v].back().fi << ' ' << ed[v].back().se << endl;
            //cout << "ha? " << v << ' ' << eversaw[v].size() << ' ' << eversaw[v].back().fi << ' ' << eversaw[v].back().se << endl;
            return true;
        }
    }
    mark[v] = 2;
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> n >> m;
    Run |= max(n, m) <= 50;
    string s; cin >> s;
    bool okk = true;
    for(int i = 0; i < s.size(); i++)
    	okk &= (s[i] == 'W' || s[i] == 'E');
    Run |= okk;
    Run ^= 1;
    string t = s;
    while(t.size() < 200000)
        t = t + s;
    s = t;
    for(int mask = 1; mask < (1 << 4); mask++){
        int last = 0;
        char av[4];
        for(int i = 0; i < 4; i++){
            if((mask >> i)&1)
                av[i] = c[i];
            else
                av[i] = 'X';
        }
        for(int i = 0; i < s.size(); i++){
            if(s[i] != av[0] && s[i] != av[1] && s[i] != av[2] && s[i] != av[3])
                last = i + 1;
            else
                mx[mask] = max(mx[mask], i - last + 1);
        }
    }
    //cout << mx[4] << endl;
    int l = 0, r = 0;
    int pt = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
    	cin >> a[i][j];
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < m; j++){
            if(!a[i][j])
                continue;
            cmp[i][j] = pt;
            av[pt].pb({i, j});
            for(int x = 0; x < 4; x++) 
                if(ok(i + adj[x].fi, j + adj[x].se) && mx[(1 << x)] >= a[i + adj[x].fi][j + adj[x].se]){
                    ed[pt].pb({i + adj[x].fi, j + adj[x].se});
            }
            //cout << i << ' ' << j << ' ' << cmp[i][j] << ' ' << ed[pt].size() << endl;
            pt++;
        }
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(a[i][j] && !mark[cmp[i][j]])
        dfs(cmp[i][j]);
    int mn = n * m + 1, cnt = 0;
    memset(mark, false, sizeof mark);
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(a[i][j] && !mark[cmp[i][j]]){
        int re = true;
        mark[cmp[i][j]] = true;
        for(auto [u, v] : eversaw[cmp[i][j]]) if(cmp[u][v] != cmp[i][j]){
        	//cout << i << ' ' << j << ' ' << cmp[i][j] << ' ' << u << ' ' << v << ' ' << cmp[u][v] << endl;
            re = false;
        }
        if(re){
        	int val = av[cmp[i][j]].size();
        	//cout << i << ' ' << j << ' ' << cmp[i][j] << ' ' << val << endl;
        	if(val < mn){
        		mn = val;
        		cnt = val;
        	}
        	else if(val == mn)
        		cnt += val;
        }
    }
    cout << mn << endl << cnt << endl;
}
 
 
 

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
virus.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int i = 0; i < s.size(); i++){
      |                        ~~^~~~~~~~~~
virus.cpp:144:9: warning: unused variable 'l' [-Wunused-variable]
  144 |     int l = 0, r = 0;
      |         ^
virus.cpp:144:16: warning: unused variable 'r' [-Wunused-variable]
  144 |     int l = 0, r = 0;
      |                ^

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80