oj.uz

Submission #818710

# Submission time Handle Problem Language Result Execution time Memory
818710 2023-08-10T06:26:18 Z fatemetmhr Virus Experiment (JOI19_virus) C++17
20 / 100
 431 ms 165832 KB 
//  ~ 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(Run)
		return 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);
	//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(!mark[cmp[i][j]])
        dfs(cmp[i][j]);
    if(Run)
    	exit(0);
    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(!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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 75296 KB Output is correct
2 Correct 431 ms 126492 KB Output is correct
3 Correct 413 ms 140236 KB Output is correct
4 Correct 198 ms 140260 KB Output is correct
5 Correct 137 ms 100156 KB Output is correct
6 Correct 304 ms 79184 KB Output is correct
7 Correct 253 ms 165832 KB Output is correct
8 Correct 78 ms 85308 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 75360 KB Output is correct
2 Correct 38 ms 75180 KB Output is correct
3 Correct 50 ms 75196 KB Output is correct
4 Correct 38 ms 75164 KB Output is correct
5 Correct 53 ms 75148 KB Output is correct
6 Correct 53 ms 76156 KB Output is correct
7 Correct 58 ms 75748 KB Output is correct
8 Correct 50 ms 75508 KB Output is correct
9 Correct 59 ms 76116 KB Output is correct
10 Correct 39 ms 75288 KB Output is correct
11 Correct 303 ms 76164 KB Output is correct
12 Correct 60 ms 76952 KB Output is correct
13 Correct 51 ms 75768 KB Output is correct
14 Correct 50 ms 75652 KB Output is correct
15 Correct 50 ms 75792 KB Output is correct
16 Correct 51 ms 75672 KB Output is correct
17 Correct 51 ms 75636 KB Output is correct
18 Correct 44 ms 75824 KB Output is correct
19 Correct 51 ms 75408 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 75296 KB Output is correct
2 Correct 431 ms 126492 KB Output is correct
3 Correct 413 ms 140236 KB Output is correct
4 Correct 198 ms 140260 KB Output is correct
5 Correct 137 ms 100156 KB Output is correct
6 Correct 304 ms 79184 KB Output is correct
7 Correct 253 ms 165832 KB Output is correct
8 Correct 78 ms 85308 KB Output is correct
9 Correct 294 ms 75360 KB Output is correct
10 Correct 38 ms 75180 KB Output is correct
11 Correct 50 ms 75196 KB Output is correct
12 Correct 38 ms 75164 KB Output is correct
13 Correct 53 ms 75148 KB Output is correct
14 Correct 53 ms 76156 KB Output is correct
15 Correct 58 ms 75748 KB Output is correct
16 Correct 50 ms 75508 KB Output is correct
17 Correct 59 ms 76116 KB Output is correct
18 Correct 39 ms 75288 KB Output is correct
19 Correct 303 ms 76164 KB Output is correct
20 Correct 60 ms 76952 KB Output is correct
21 Correct 51 ms 75768 KB Output is correct
22 Correct 50 ms 75652 KB Output is correct
23 Correct 50 ms 75792 KB Output is correct
24 Correct 51 ms 75672 KB Output is correct
25 Correct 51 ms 75636 KB Output is correct
26 Correct 44 ms 75824 KB Output is correct
27 Correct 51 ms 75408 KB Output is correct
28 Incorrect 224 ms 148636 KB Output isn't correct
29 Halted 0 ms 0 KB -