QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657908#5668. Cell Nuclei Detectionucup-team5234#AC ✓1212ms162676kbC++234.4kb2024-10-19 15:43:022024-10-19 15:43:02

Judging History

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

  • [2024-10-19 15:43:02]
  • 评测
  • 测评结果:AC
  • 用时:1212ms
  • 内存:162676kb
  • [2024-10-19 15:43:02]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using vvi = vector<vector<int>>;
using vb = vector<bool>;
using vi = vector<int>;

namespace atcoder {
    template <class Cap> struct mf_graph {
        public:
        mf_graph(int n) : _n(n), g(n) {}

        int add_edge(int from, int to, Cap cap){
            int m = int(pos.size());
            pos.push_back({from, int(g[from].size())});
            int from_id = int(g[from].size());
            int to_id = int(g[to].size());
            if(from == to)to_id++;
            g[from].push_back(_edge{to, to_id, cap});
            g[to].push_back(_edge{from, from_id, 0});
            return m;
        }

        struct edge {
            int from, to;
            Cap cap, flow;
        };

        Cap flow(int s, int t){
            return flow(s, t, numeric_limits<Cap>::max());
        }

        Cap flow(int s, int t, Cap flow_limit) {
            vi level(_n), iter(_n);
            queue<int> que;
            auto bfs = [&](){
                fill(level.begin(),level.end(), -1);
                level[s] = 0;
                while(!que.empty())que.pop();
                que.push(s);
                while(!que.empty()){
                    int v = que.front();
                    que.pop();
                    for(auto e : g[v]){
                        if(e.cap == 0 || level[e.to] >= 0)continue;
                        level[e.to] = level[v] + 1;
                        if(e.to== t)return;
                        que.push(e.to);
                    }
                }
            };
            auto dfs = [&](auto self, int v, Cap up){
                if(v == s)return up;
                Cap res = 0;
                int level_v = level[v];
                for(int& i = iter[v]; i < int(g[v].size()); i++){
                    _edge& e = g[v][i];
                    if(level_v <= level[e.to] || g[e.to][e.rev].cap == 0)continue;
                    Cap d = self(self, e.to, min(up - res, g[e.to][e.rev].cap));
                    if(d <= 0)continue;
                    g[v][i].cap += d;
                    g[e.to][e.rev].cap -= d;
                    res += d;
                    if(res == up)break;
                }
                return res;
            };
            Cap flow = 0;
            while(flow < flow_limit){
                bfs();
                if(level[t] == -1)break;
                fill(iter.begin(), iter.end(), 0);
                while(flow < flow_limit) {
                    Cap f = dfs(dfs, t, flow_limit - flow);
                    if(!f)break;
                    flow += f;
                }
            } 
            return flow;
        }
        private:
    int _n;
    struct _edge {
        int to, rev;
        Cap cap;
    };
    vector<pair<int,int>> pos;
    vector<vector<_edge>> g;
    };
};

using namespace atcoder;

int main(){
    int t;
    cin >> t;
    while(t -- ){
        int m,n;
        cin >> m >> n;
        vector<vector<vi>> v(2010,vvi(2010));
        vector<int> sz(m);
        for(int i = 0; i < m; i++){
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            sz[i] = (x2-x1) * (y2-y1);
            for(int x = x1; x < x2; x++){
                for(int y = y1; y < y2; y++){
                    v[x][y].push_back(i);
                }
            }
        }
        vector<int> cnt(m);
        mf_graph<ll> g(m + n + 2);
        int s = m + n;
        int t = s + 1;
        for(int i = 0; i < m; i++)g.add_edge(s, i, 1);
        for(int i = 0; i < n; i++)g.add_edge(i + m, t, 1);
        for(int i = 0; i < n; i++){
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            set<int> S;
            for(int x = x1; x < x2; x++){
                for(int y = y1; y < y2; y++){
                    for(auto e: v[x][y]){
                        S.insert(e);
                        cnt[e]++;
                    }
                }
            }
            for(auto e: S){
                // cout << e << " " << i << " " << cnt[e] << " " << sz[e] << endl;
                if(sz[e] <= 2 * cnt[e]){
                    // cout << "!" << e << " " << i << endl;
                    g.add_edge(e, m + i, 1);
                }
                cnt[e] = 0;
            }
        }
        cout << g.flow(s, t) << endl;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 51ms
memory: 97888kb

input:

3
2 2
1 1 3 3
3 3 5 5
2 2 4 4
4 4 6 6
2 3
1 1 3 3
3 3 5 5
1 3 3 5
2 1 4 5
3 1 5 3
3 3
1 1 2 2
2 2 3 3
3 3 4 4
1 1 3 3
2 2 4 4
3 3 5 5

output:

0
1
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 39ms
memory: 97956kb

input:

3
2 2
1 1 3 3
3 3 5 5
2 2 4 4
4 4 6 6
2 3
1 1 3 3
3 3 5 5
1 3 3 5
2 1 4 5
3 1 5 3
3 3
1 1 2 2
2 2 3 3
3 3 4 4
1 1 3 3
2 2 4 4
3 3 5 5

output:

0
1
3

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 638ms
memory: 145420kb

input:

5
50000 50000
0 0 4 4
4 0 8 4
8 0 12 4
12 0 16 4
16 0 20 4
20 0 24 4
24 0 28 4
28 0 32 4
32 0 36 4
36 0 40 4
40 0 44 4
44 0 48 4
48 0 52 4
52 0 56 4
56 0 60 4
60 0 64 4
64 0 68 4
68 0 72 4
72 0 76 4
76 0 80 4
80 0 84 4
84 0 88 4
88 0 92 4
92 0 96 4
96 0 100 4
100 0 104 4
104 0 108 4
108 0 112 4
112 ...

output:

50000
50000
0
50000
3150

result:

ok 5 lines

Test #4:

score: 0
Accepted
time: 539ms
memory: 162676kb

input:

5
50000 50000
0 0 1 1
1 0 2 1
2 0 3 1
3 0 4 1
4 0 5 1
5 0 6 1
6 0 7 1
7 0 8 1
8 0 9 1
9 0 10 1
10 0 11 1
11 0 12 1
12 0 13 1
13 0 14 1
14 0 15 1
15 0 16 1
16 0 17 1
17 0 18 1
18 0 19 1
19 0 20 1
20 0 21 1
21 0 22 1
22 0 23 1
23 0 24 1
24 0 25 1
25 0 26 1
26 0 27 1
27 0 28 1
28 0 29 1
29 0 30 1
30 0 ...

output:

50000
25050
12500
16000
8000

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 489ms
memory: 119140kb

input:

5
50000 50000
0 0 2 4
4 0 7 1
8 0 10 1
12 0 15 3
16 0 19 1
20 0 22 2
24 0 26 4
28 0 30 4
32 0 36 3
36 0 40 1
40 0 44 1
44 0 47 2
48 0 49 3
52 0 54 1
56 0 59 4
60 0 64 3
64 0 68 3
68 0 70 1
72 0 76 4
76 0 80 3
80 0 84 4
84 0 87 2
88 0 90 1
92 0 94 4
96 0 98 1
100 0 104 1
104 0 107 2
108 0 110 4
112 0...

output:

10594
10779
10618
10381
10779

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 1212ms
memory: 143296kb

input:

5
50000 50000
0 0 4 4
1 0 5 4
2 0 6 4
3 0 7 4
4 0 8 4
5 0 9 4
6 0 10 4
7 0 11 4
8 0 12 4
9 0 13 4
10 0 14 4
11 0 15 4
12 0 16 4
13 0 17 4
14 0 18 4
15 0 19 4
16 0 20 4
17 0 21 4
18 0 22 4
19 0 23 4
20 0 24 4
21 0 25 4
22 0 26 4
23 0 27 4
24 0 28 4
25 0 29 4
26 0 30 4
27 0 31 4
28 0 32 4
29 0 33 4
30...

output:

50000
50000
50000
50000
49600

result:

ok 5 lines

Test #7:

score: 0
Accepted
time: 19ms
memory: 97856kb

input:

1
4 4
1 1 3 3
2 1 4 3
1 2 3 4
2 2 4 4
2 1 4 3
3 2 5 4
1 2 3 4
2 3 4 5

output:

3

result:

ok single line: '3'