oj.uz

Submission #732376

# Submission time Handle Problem Language Result Execution time Memory
732376 2023-04-29T03:03:23 Z vjudge1 Collecting Mushrooms (NOI18_collectmushrooms) C++17
0 / 100
 706 ms 34664 KB 
#include <bits/stdc++.h>
#define sts stable_sort
#define B begin()
#define rB rbegin()
#define E end()
#define rE rend()
#define F first
#define S second
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define eb emplace_back
#define ll long long
#define ui unsigned int
#define ull unsigned long long

using namespace std;

const int MAXN = 500004;
const int MOD = 1e9 + 7;
const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
map<pair<int, int>, int> ma;

void bfs(pair<int, int> z, int r, int c, int d){

    queue<pair<pair<int, int>, int> > q;
    bool comp[r + 1][c + 1];
    comp[z.F][z.S] = 0;
    q.push({z, 0});

    while(!q.empty()){
        pair<pair<int, int>, int> x = q.front();
        q.pop();
//        cout << x.F.F << " " << x.F.S << "\n";
//        cout << r << " " << c << "\n" << "\n";
        if( x.F.F <= 0 || x.F.F > r || x.F.S <= 0 || x.F.S > c || x.S > d)continue;
//        cout << comp[x.F.F][x.F.S] << "\n";
        if(comp[x.F.F][x.F.S])continue;
        comp[x.F.F][x.F.S] = 1;
        ma[x.F]++;
//        cout << ma[x.F] << "\n";

        q.push({{x.F.F + 1, x.F.S}, x.S + 1});
        q.push({{x.F.F - 1, x.F.S}, x.S + 1});
        q.push({{x.F.F, x.F.S + 1},x.S + 1});
        q.push({{x.F.F, x.F.S - 1},x.S + 1});
        q.push({{x.F.F + 1, x.F.S - 1},x.S + 1});
        q.push({{x.F.F + 1, x.F.S + 1},x.S + 1});
        q.push({{x.F.F - 1, x.F.S - 1},x.S + 1});
        q.push({{x.F.F - 1, x.F.S + 1},x.S + 1});
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    int r, c, d, k; cin >> r >> c >> d >> k;

    vector<pair<int, int> > s;
    vector<pair<int, int> > m;

    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            char ch; cin >> ch;
            if(ch == 'S'){
                s.pb({i, j});
            }else if(ch == 'M'){
                m.pb({i, j});
            }
        }
    }

    for(int i = 0; i < s.size(); i++){
        bfs(s[i], r, c, d);
    }
    int cnt = 0;
    for(int i = 0; i < m.size(); i++){
        if(ma[m[i]] >= k)cnt++;
    }cout << cnt << "\n";

    return 0;
}
/**



**/

Compilation message

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
mushrooms.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < m.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 12684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 706 ms 34664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -