QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#657908 | #5668. Cell Nuclei Detection | ucup-team5234# | AC ✓ | 1212ms | 162676kb | C++23 | 4.4kb | 2024-10-19 15:43:02 | 2024-10-19 15:43:02 |
Judging History
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'