QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106337#6308. MagicGeZhiyuanRE 0ms0kbC++141.8kb2023-05-17 14:24:442023-05-17 14:24:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 14:24:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-05-17 14:24:44]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

5
2 3
6 7
1 9
5 10
4 8

output:


result: