QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371186#6526. CanvasNelofusWA 8ms36856kbC++203.4kb2024-03-30 01:31:542024-03-30 01:31:55

Judging History

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

  • [2024-03-30 01:31:55]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:36856kb
  • [2024-03-30 01:31:54]
  • 提交

answer

/*
 * Copyright© 2024 Heratino & Nelofus. All rights reserved.
 * author: Heratino & Nelofus
 * Problem: 
 * Tag: 
 * Memory Limit: 
 * Time Limit: 
 * Source: 
 */

// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

constexpr int N = 5e5 + 10;
struct operators {
	int l, r, x, y;
	int type;
	int id;
} qry[N];
int n, m;
int dfn[N], low[N], dfc, sn;
int number[N];
bool instk[N];
int stk[N], tt;
std::basic_string<int> scc[N];
std::vector<operators> edg[N];
std::basic_string<int> G[N];

void dfs(int u) {
	dfn[u] = low[u] = ++dfc;
	stk[++tt] = u;
	instk[u] = true;
	for (const int &v : G[u]) {
		if (!dfn[v]) {
			dfs(v);
			low[u] = std::min(low[u], low[v]);
		} else if (instk[v]) {
			low[u] = std::min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		sn++;
		while (stk[tt] != u) {
			instk[stk[tt]] = false;
			number[stk[tt]] = sn;
			scc[sn].push_back(stk[tt--]);
		}
		instk[stk[tt]] = false;
		number[stk[tt]] = sn;
		scc[sn].push_back(stk[tt--]);
	}
}

void tarjan() {
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			dfs(i);
}

int ans[N];
int ind[N];
int tp[N];
int dis[N];
void clear(int n, int m) {
	for (int i = 1; i <= n; i++)	G[i].clear();
	for (int i = 1; i <= sn; i++)	scc[i].clear();
	memset(dfn + 1, 0, n * sizeof(int));
	memset(low + 1, 0, n * sizeof(int));
	memset(ans + 1, 0, n * sizeof(int));
	memset(ind + 1, 0, n * sizeof(int));
	dfc = 0, sn = 0;

	memset(dis + 1, 0x3f, n * sizeof(int));
}

inline void add(int u, int v) {G[u] += v;}

void bfs() {
	std::queue<int> q;
	dfc = 0;
	for (int i = 1; i <= sn; i++)
		if (ind[i] == 0)
			q.push(scc[i][0]), dis[scc[i][0]] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (const int &v : G[u]) {
			if (dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
}

void solve() {
	std::cin >> n >> m;
	clear(n, m);
	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qry[i];
		std::cin >> l >> x >> r >> y;
		if (x == 1 && y == 1)
			type = 0;
		else if (x == 2 && y == 2)
			type = 2;
		else
			type = 1;
		id = i;
	}
	std::sort(qry + 1, qry + 1 + m, [&](operators a, operators b) {
			return a.type < b.type;
			});
	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qry[i];
		if (x == 1 && y == 2)
			add(r, l);
		if (x == 2 && y == 1)
			add(l, r);
	}

	tarjan();

	for (int u = 1; u <= n; u++)
		for (const int &v : G[u]) {
			if (number[u] != number[v]) {
				ind[number[v]]++;
			}
		}
	bfs();

	std::sort(qry + 1, qry + 1 + m, [&](operators a, operators b) {
			if (a.type == 1 && b.type == 1) {
				int t1 = (a.x == 1 ? a.l : a.r);
				int t2 = (b.x == 1 ? b.l : b.r);
				return dis[t1] < dis[t2];
			}
			return a.type < b.type;
			});
	for (int i = m; i >= 1; i--) {
		auto &[l, r, x, y, type, id] = qry[i];
		if (ans[l] == 0)
			ans[l] = x;
		if (ans[r] == 0)
			ans[r] = y;
	}
	int res = 0;
	for (int i = 1; i <= n; i++)
		res += ans[i];
	std::cout << res << '\n';
	// 正序输出
	for (int i = 1; i <= m; i++)
		std::cout << qry[i].id << " \n"[i == m];
}

/* 无法忘却的记忆与苍蓝之梦 */
int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 36140kb

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 1 2 3
5
2 1

result:

ok Correct. (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 8ms
memory: 36856kb

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:

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

result:

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