oj.uz

Submission #818781

# Submission time Handle Problem Language Result Execution time Memory
818781 2023-08-10T06:43:34 Z fatemetmhr Virus Experiment (JOI19_virus) C++17
20 / 100
 446 ms 262144 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], gooded[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);
	//cout << "here merge of " << a << ' ' << b << endl;
    return a;
}

int dfs(int v){
    mark[v] = 1;
    bool tomerge = false;
    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]){
        	int x;
            if((x = dfs(u)) != -1){
                v = merge(x, v);
            }
            mark[v] = 1;
        }
        else if(mark[u] == 1){
        	tomerge = true;
        	gooded[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;
        }
    }
    for(auto p : gooded[v])
    	ed[v].pb(p);
    gooded[v].clear();
    gooded[v].shrink_to_fit();
    mark[v] = 2;
    return (tomerge ? v : -1);
}

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98720 KB Output is correct
2 Correct 446 ms 149976 KB Output is correct
3 Correct 435 ms 163764 KB Output is correct
4 Correct 214 ms 163636 KB Output is correct
5 Correct 131 ms 123608 KB Output is correct
6 Correct 320 ms 102612 KB Output is correct
7 Correct 307 ms 208436 KB Output is correct
8 Correct 87 ms 108816 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 98768 KB Output is correct
2 Correct 49 ms 98744 KB Output is correct
3 Correct 61 ms 98756 KB Output is correct
4 Correct 51 ms 98740 KB Output is correct
5 Correct 62 ms 98724 KB Output is correct
6 Correct 66 ms 100864 KB Output is correct
7 Correct 72 ms 99504 KB Output is correct
8 Correct 69 ms 98980 KB Output is correct
9 Correct 72 ms 100012 KB Output is correct
10 Correct 50 ms 98632 KB Output is correct
11 Correct 316 ms 99672 KB Output is correct
12 Correct 73 ms 100872 KB Output is correct
13 Correct 68 ms 99344 KB Output is correct
14 Correct 61 ms 99256 KB Output is correct
15 Correct 63 ms 99552 KB Output is correct
16 Correct 63 ms 99128 KB Output is correct
17 Correct 61 ms 99120 KB Output is correct
18 Correct 56 ms 99308 KB Output is correct
19 Correct 62 ms 98948 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98720 KB Output is correct
2 Correct 446 ms 149976 KB Output is correct
3 Correct 435 ms 163764 KB Output is correct
4 Correct 214 ms 163636 KB Output is correct
5 Correct 131 ms 123608 KB Output is correct
6 Correct 320 ms 102612 KB Output is correct
7 Correct 307 ms 208436 KB Output is correct
8 Correct 87 ms 108816 KB Output is correct
9 Correct 310 ms 98768 KB Output is correct
10 Correct 49 ms 98744 KB Output is correct
11 Correct 61 ms 98756 KB Output is correct
12 Correct 51 ms 98740 KB Output is correct
13 Correct 62 ms 98724 KB Output is correct
14 Correct 66 ms 100864 KB Output is correct
15 Correct 72 ms 99504 KB Output is correct
16 Correct 69 ms 98980 KB Output is correct
17 Correct 72 ms 100012 KB Output is correct
18 Correct 50 ms 98632 KB Output is correct
19 Correct 316 ms 99672 KB Output is correct
20 Correct 73 ms 100872 KB Output is correct
21 Correct 68 ms 99344 KB Output is correct
22 Correct 61 ms 99256 KB Output is correct
23 Correct 63 ms 99552 KB Output is correct
24 Correct 63 ms 99128 KB Output is correct
25 Correct 61 ms 99120 KB Output is correct
26 Correct 56 ms 99308 KB Output is correct
27 Correct 62 ms 98948 KB Output is correct
28 Runtime error 318 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -