QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134215#1076. Flooding FieldsChatGPTRE 0ms0kbC++232.2kb2023-08-03 13:42:582023-08-03 13:43:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 13:43:03]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-08-03 13:42:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
const int INF = 1e9;
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1}; // up, right, down, left
int grid[105][105], dist[105][105], n;
vector<pii> cows;
priority_queue<pii, vector<pii>, greater<pii>> pq;

bool valid(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < n;
}

void bfs() {
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            dist[i][j] = INF;
    for(pii cow : cows)
        dist[cow.first][cow.second] = grid[cow.first][cow.second], pq.push({grid[cow.first][cow.second], cow.first*n + cow.second});
    while(!pq.empty()) {
        pii top = pq.top();
        pq.pop();
        int d = top.first, r = top.second / n, c = top.second % n;
        if(dist[r][c] != d)
            continue;
        for(int dir=0; dir<4; ++dir) {
            int nr = r + dr[dir], nc = c + dc[dir];
            if(!valid(nr, nc) || min(d, grid[nr][nc]) < dist[nr][nc])
                dist[nr][nc] = min(d, grid[nr][nc]), pq.push({dist[nr][nc], nr*n + nc});
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k, h;
    while(cin >> n >> k >> h, n || k || h) {
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                cin >> grid[i][j];
        cows.clear();
        while(k--) {
            int r, c;
            cin >> r >> c;
            cows.push_back({r, c});
        }
        bfs();
        int water[25];
        for(int i=0; i<h; ++i)
            cin >> water[i];
        water[h] = INF;
        sort(water, water+h+1);
        vector<pii> cells;
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
                cells.push_back({dist[i][j], i*n + j});
        sort(cells.begin(), cells.end());
        int ans = 0, ptr = 0;
        priority_queue<int> pq;
        for(int i=0; i<=h; ++i) {
            while(ptr < cells.size() && cells[ptr].first <= water[i])
                pq.push(grid[cells[ptr].second / n][cells[ptr].second % n]), ++ptr;
            while(!pq.empty() && pq.top() <= water[i])
                pq.pop();
            if(!pq.empty())
                ++ans, pq.pop();
        }
        cout << ans << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

3 1 3
2 1 2
3 1 3
2 4 2
1 1
0
2
1
2 4 2
0 1
1 2
0 0
0 1
1 1
1 0
1
0
50 50 24
5 20 21 3 2 9 22 15 19 22 18 14 19 14 15 4 22 22 7 12 7 2 2 0 25 0 7 6 4 3 2 17 1 12 7 12 1 19 12 3 23 5 5 10 22 15 17 3 13 4
10 21 7 12 10 22 23 18 17 5 17 18 2 14 12 13 13 19 19 18 8 11 3 0 24 0 6 1 9 12 14 13 20 22 5 13 ...

output:


result: