QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#106337 | #6308. Magic | GeZhiyuan | RE | 0ms | 0kb | C++14 | 1.8kb | 2023-05-17 14:24:44 | 2023-05-17 14:24:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
class section{
public:
int l, r;
inline section() {}
inline section(int l_, int r_){
l = l_, r = r_;
}
};
class node{
public:
int opt, x;
inline node() {}
inline node(int opt_, int x_){
opt = opt_, x = x_;
}
};
const int N = 5000 + 5, Inf = 0x3f3f3f3f;
int n = 0, dis[2][N] = {}, vis[2][N] = {};
bitset<N> G[2][N] = {}, S, T;
queue<node> Q;
section sec[N] = {};
inline bool bfs(){
memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis));
for(int u = 1 ; u <= n ; u ++) if(S[u]){
dis[0][u] = 1;
Q.push(node(0, u));
}
while(Q.size()){
int opt = Q.front().opt, u = Q.front().x; Q.pop();
for(int v = 1 ; v <= n ; v ++) if(G[opt][u][v] && dis[opt ^ 1][v] == Inf){
dis[opt ^ 1][v] = dis[opt][u] + 1;
Q.push(node(opt ^ 1, v));
}
}
for(int u = 1 ; u <= n ; u ++) if(T[u] && dis[1][u] != Inf) return 1;
return 0;
}
inline bool dfs(int opt, int u){
vis[opt][u] = 1;
if(opt && T[u]){
T[u] = 0;
return 1;
}
for(int v = 1 ; v <= n ; v ++) if(!vis[opt ^ 1][v] && G[opt][u][v] && dis[opt][u] + 1 == dis[opt ^ 1][v] && dfs(opt ^ 1, v)){
G[opt][u][v] = 0, G[opt ^ 1][v][u] = 1;
return 1;
}
return 0;
}
inline int Dinic(){
int ret = 0;
while(bfs()) for(int u = 1 ; u <= n ; u ++) if(S[u] && !vis[0][u] && dfs(0, u)){
S[u] = 0;
ret ++;
}
return ret;
}
int main(){
freopen("frog.in", "r", stdin);
freopen("frog.out", "w", stdout);
scanf("%d", &n);
for(int i = 1 ; i <= n ; i ++) scanf("%d %d", &sec[i].l, &sec[i].r);
for(int i = 1 ; i <= n ; i ++){
S[i] = T[i] = 1;
for(int j = 1 ; j <= n ; j ++) if(sec[i].l < sec[j].l && sec[j].l < sec[i].r && sec[i].r < sec[j].r) G[0][i][j] = 1;
}
printf("%d", 2 * n - Dinic());
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
5 2 3 6 7 1 9 5 10 4 8