QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138354#6526. Canvasneko_nyaa#WA 1ms3588kbC++231.8kb2023-08-11 16:14:432023-08-11 16:14:44

Judging History

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

  • [2023-08-11 16:14:44]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3588kb
  • [2023-08-11 16:14:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;

void solve() {
	int n, m; cin >> n >> m;
	vector<vector<pair<int, int>>> adj(n+1);
	vector<int> scr(n+1);
	vector<int> bade, goode;
	vector<tuple<int, int, int, int>> ops;
	for (int i = 1; i <= m; i++) {
		int u, x, v, y; cin >> u >> x >> v >> y;
		ops.emplace_back(u, x, v, y);
		if (x == 1 && y == 1) {
			bade.push_back(i);
		} else if (x == 2 && y == 2) {
			goode.push_back(i);
			scr[u] = scr[v] = 1;
		} else {
			if (x == 2) {
				swap(u, v);
			}
			adj[x].emplace_back(y, i);
		}
	}

	vector<int> visord;
	vector<int> indeg(n+1);
	for (int i = 1; i <= n; i++) {
		for (auto [j, id]: adj[i]) {
			indeg[j]++;
		}
	}

	vector<int> seen(n+1);
	set<pair<int, int>> cands;
	for (int i = 1; i <= n; i++) {
		if (scr[i]) {
			cands.insert({-1, i});
		} else {
			cands.insert({indeg[i], i});
		}
	}

	for (int _ = 0; _ < n; _++) {
		auto [indg, u] = *cands.begin(); 
		seen[u] = 1; cands.erase(cands.begin());
		//cout << u << endl;

		for (auto [v, id]: adj[u]) {
			visord.push_back(id);
			if (scr[v]) continue;
			if (seen[v]) continue;
			cands.erase(cands.find({indeg[v], v}));
			indeg[v]--;
			cands.insert({indeg[v], v});
		}
	}
	reverse(visord.begin(), visord.end());

	// answer
	vector<int> ans;
	for (int i: bade) ans.push_back(i);
	for (int i: visord) ans.push_back(i);
	for (int i: goode) ans.push_back(i);

	vector<int> fl(n+1);
	for (int i: ans) {
		auto [u, x, v, y] = ops[i-1];
		fl[u] = x; fl[v] = y;
	}

	cout << accumulate(fl.begin(), fl.end(), 0LL) << '\n';
	for (int i: ans) cout << i << ' ';
		cout << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int t; cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

詳細信息

Test #1:

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

input:

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

output:

7
4 2 1 3 
5
2 1 

result:

ok Correct. (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3588kb

input:

1
10 13
1 1 2 2
2 1 3 2
1 2 3 1
3 1 4 2
4 1 5 2
5 1 6 2
4 2 6 1
7 1 8 2
8 1 9 2
7 2 9 1
5 2 9 1
8 2 10 2
1 1 10 1

output:

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

result:

wrong answer Jury has better answer. Participant 18, jury 19 (test case 1)