QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#874646#8131. FilesystemlouisliangWA 1ms3840kbC++142.1kb2025-01-28 12:54:142025-01-28 12:54:16

Judging History

This is the latest submission verdict.

  • [2025-01-28 12:54:16]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3840kb
Show
  • [2025-01-28 12:54:14]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1005, M = 10005;
int n, m, head[N], vi[M], wi[M], ne[M], tot, a[N], p[N];
int s, t, dis[N], cur[N];
bool b[N];
void addedge(int u, int v, int w){
	ne[++tot] = head[u], vi[tot] = v, wi[tot] = w, head[u] = tot;
}
void add(int u, int v, int w){
//	cout << u << " " << v << "\n";
	addedge(u, v, w);
	addedge(v, u, w);
}
queue <int> q;
bool bfs(){
	memset(dis, -1, sizeof(dis));
	dis[s] = 0;
	while(!q.empty())
		q.pop();
	q.push(s);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i = head[x]; i; i = ne[i]){
			int y = vi[i];
			if(dis[y] == -1 && wi[i]){
				dis[y] = dis[x] + 1;
				if(y == t)
					return 1;
				q.push(y);
			}
		}
	}
	return 0;
}
int dfs(int x, int lim){
	if(x == t)
		return lim;
	int flow = 0;
	for(int &i = cur[x]; i; i = ne[i]){
		int y = vi[i];
		if(dis[y] != dis[x] + 1 || !wi[i])
			continue;
		int dlt = dfs(y, min(lim - flow, wi[i]));
		wi[i] -= dlt, flow += dlt, wi[i ^ 1] += dlt;
		if(flow == lim)
			break;
	}
	return flow;
}
int dinic(){
	int flow, sum = 0;
	while(bfs()){
		memcpy(cur, head, sizeof(int) * (n + 1));
		while((flow = dfs(s, 1e9)))
			sum += flow;
	}
	return sum;
}
int main(){
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Cases;
	cin >> Cases;
	while(Cases--){
		cin >> n >> m;
		tot = 1, s = 0, t = n + 1;
		memset(head, 0, sizeof(int) * (t + 1));
		memset(b, 0, sizeof(bool) * (n + 1));
		for(int i = 1, x; i <= m; i++){
			cin >> x;
			b[x] = 1;
		}
		int cnt = 2 * m;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			p[i] = i;
			if(b[a[i]] && b[a[i - 1]]){
				cnt -= 2;
				add(s, i, 1);
				add(s, i - 1, 1);
				add(i, i - 1, 1);
				add(i - 1, i, 1);
			}
		}
		sort(p + 1, p + n + 1, [](int x, int y){return a[x] < a[y];});
		for(int i = 2; i <= n; i++){
			if(b[a[p[i]]] && b[a[p[i - 1]]]){
				cnt -= 2;
				add(p[i], t, 1);
				add(p[i - 1], t, 1);
				add(p[i], p[i - 1], 1);
				add(p[i - 1], p[i], 1);
			}
		}
		cout << (cnt + dinic()) / 2 << "\n";
	}
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

2
12 8
2 5 8 3 4 10 12 1
10 5 8 6 4 7 2 3 11 12 1 9
8 4
1 3 5 7
1 4 5 8 7 6 3 2

output:

3
4

result:

ok 2 number(s): "3 4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

100
10 3
10 5 2
2 4 9 8 7 3 1 5 10 6
10 3
8 1 10
8 4 3 7 1 2 9 5 6 10
10 3
6 5 2
8 7 6 4 2 10 1 3 5 9
10 3
5 8 4
10 4 5 7 8 9 1 2 3 6
10 3
8 4 10
10 6 9 2 8 7 1 4 3 5
10 3
9 8 1
8 5 6 10 2 4 1 7 9 3
10 3
5 4 1
7 5 8 4 3 6 9 10 2 1
10 3
2 4 3
6 7 3 9 1 2 5 8 4 10
10 3
9 5 3
6 10 7 4 9 3 1 8 5 2
10 3
...

output:

2
3
2
2
3
2
2
1
2
2
3
2
2
2
2
2
2
2
3
2
2
2
2
2
2
2
2
3
1
3
1
2
2
2
2
2
2
2
3
2
2
3
3
3
2
2
2
3
2
2
2
2
2
2
3
2
2
2
2
2
3
2
2
1
2
1
2
2
2
1
3
2
3
1
2
2
3
2
2
3
3
2
3
2
2
2
2
3
2
2
2
2
3
1
3
3
2
2
2
2

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

100
10 5
2 6 1 9 3
10 8 2 6 9 7 5 1 3 4
10 5
7 10 1 3 6
5 7 3 9 4 1 8 2 10 6
10 5
8 3 6 2 9
4 2 9 3 8 1 6 10 7 5
10 5
5 6 7 4 3
3 7 6 2 1 5 9 8 10 4
10 5
1 6 8 10 5
8 6 3 10 1 4 7 9 5 2
10 5
6 5 1 3 9
8 10 5 3 6 1 9 2 7 4
10 5
8 6 2 7 1
3 6 5 10 9 1 2 7 4 8
10 5
6 10 8 4 2
3 9 7 5 4 1 10 6 2 8
10 5
...

output:

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

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

100
10 8
3 4 9 1 8 7 2 10
9 1 7 10 5 6 2 4 8 3
10 8
9 1 8 4 2 10 3 7
4 9 8 3 7 10 2 1 5 6
10 8
4 8 3 6 9 10 7 1
10 3 5 1 6 4 8 9 2 7
10 8
2 4 5 9 7 3 10 8
10 7 2 9 3 4 8 6 1 5
10 8
3 1 8 5 9 2 10 6
10 9 2 7 1 8 3 5 4 6
10 8
10 9 3 5 6 4 7 2
1 10 2 4 7 5 8 3 9 6
10 8
7 1 8 9 2 10 5 4
2 4 10 3 6 1 8 7...

output:

2
1
3
2
3
2
2
2
2
3
2
1
1
2
2
2
2
2
2
3
3
3
2
2
2
3
2
2
2
2
3
2
2
3
2
2
2
2
2
2
2
3
2
2
1
2
1
3
2
2
2
2
2
2
3
2
3
2
3
2
2
2
1
2
1
2
2
2
1
2
2
2
2
3
1
2
3
2
3
2
3
2
2
3
3
2
3
2
2
2
2
2
2
3
2
2
2
3
2
2

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

50
20 5
19 14 5 12 6
4 16 6 13 20 8 18 17 14 19 12 3 11 9 15 1 10 7 5 2
20 5
2 17 9 7 13
9 10 4 5 1 2 19 12 14 20 11 16 7 3 17 6 18 15 13 8
20 5
16 12 8 4 7
18 13 11 19 8 17 16 10 4 9 7 2 14 20 15 5 12 1 3 6
20 5
9 4 14 6 5
5 9 11 18 14 10 1 12 16 19 4 20 8 15 6 17 13 3 7 2
20 5
6 9 2 17 15
3 20 17 ...

output:

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

result:

ok 50 numbers

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3840kb

input:

50
20 10
12 3 2 7 14 20 17 6 19 16
8 19 9 13 12 16 6 11 5 17 3 4 14 7 15 1 10 20 18 2
20 10
12 15 18 4 11 3 2 14 13 6
11 17 12 16 10 19 18 2 15 3 9 6 14 1 5 20 7 8 13 4
20 10
5 1 6 10 12 19 7 11 8 3
17 7 9 16 3 10 11 5 14 12 13 2 19 15 1 18 6 20 4 8
20 10
19 11 5 15 7 16 17 9 2 18
7 15 20 8 11 19 16...

output:

5
4
5
4
4
4
6
5
5
4
5
4
5
5
4
3
5
6
4
4
5
4
4
5
4
4
5
6
5
5
4
6
4
3
5
4
4
5
4
5
4
4
4
6
3
4
5
4
4
7

result:

wrong answer 12th numbers differ - expected: '3', found: '4'
English 繁體中文 简体中文

伺服器時間: 2025-02-05 16:45:56 | 開源專案