QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114878#6526. CanvasxaphoenixWA 11ms77292kbC++144.4kb2023-06-23 20:34:102023-06-23 20:34:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-23 20:34:11]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:77292kb
  • [2023-06-23 20:34:10]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 510000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int T, n, m, a[N];
struct inst {
	int id, l, r, x, y;
	void read(int d) {
		id = d;
		cin >> l >> x >> r >> y;
	}
}b[N];
int st1[N], st2[N];
vector<int> f[N], h[N];
vector<PII> g[N];
int t1, t2, pp[N], cp[N], qp[N], du[N], fp[N];
queue<int> que;

int dfn[N], low[N], instack[N], scc[N], cnt, scc_cnt;
stack<int> st;
vector<int> sc[N];
void tarjan(int x) {
	dfn[x] = low[x] = ++cnt;
	st.push(x);
	instack[x] = 1;
	for (auto p: g[x]) {
		int y = p.fi;
		if (dfn[y]==0) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (instack[y]) low[x] = min(low[x], dfn[y]);
	}
	if (low[x]==dfn[x]) {
		++scc_cnt;
		while (!st.empty() && st.top() != x) {
			scc[st.top()] = scc_cnt;
			instack[st.top()] = 0;
			st.pop();
		}
		st.pop();
		scc[x] = scc_cnt;
		instack[x] = 0;
	}
}
vector<int> ans;
void dfs(int x) {
	fp[x] = 1;
	for (auto p: g[x]) {
		int y = p.fi, id = p.se;
		if (scc[y] == scc[x]);
		else st2[++t2] = id;
	}
	for (auto p: g[x]) {
		int y = p.fi, id = p.se;
		if (scc[y] == scc[x]) {
			if (fp[y]) st1[++t1] = id;
			else st2[++t2] = id, dfs(y);
		}
	}
}
int main() {
	IO;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		cnt = scc_cnt = 0;
		repn(i, 1, n) a[i] = pp[i] = dfn[i] = qp[i] = du[i] = fp[i] = 0, f[i].clear(), g[i].clear(), sc[i].clear(), h[i].clear();
		repn(i, 1, m) cp[i] = 0;
		t1 = t2 = 0;
		while (!que.empty()) que.pop();
		repn(i, 1, m) {
			b[i].read(i);
			if (b[i].x == 2 && b[i].y == 2) {
				cp[b[i].id] = 1;
				st2[++t2] = i;
				if (!pp[b[i].l]) pp[b[i].l] = 1, que.push(b[i].l);
				if (!pp[b[i].r]) pp[b[i].r] = 1, que.push(b[i].r);
			}
			else if (b[i].x == 1 && b[i].y == 1) {
				cp[b[i].id] = 1;
				st1[++t1] = i;
			}
			else {
				f[b[i].l].pb(i), f[b[i].r].pb(i);
			}
		}
		while (!que.empty()) {
			int now = que.front(); que.pop();
			for (auto x: f[now]) {
				auto p = b[x];
				if (cp[p.id]) continue;
				cp[p.id] = 1;
				if (p.l == now) {
					if (p.x == 1) {
						st2[++t2] = p.id;
						if (!pp[p.r]) pp[p.r] = 1, que.push(p.r);
					}
					else st1[++t1] = p.id;
				}
				else {
					if (p.y == 1) {
						st2[++t2] = p.id;
						if (!pp[p.l]) pp[p.l] = 1, que.push(p.l);
					}
					else st1[++t1] = p.id;
				}
			}
		}
		repn(i, 1, m) {
			if (!cp[b[i].id]) {
				if (b[i].x == 1) g[b[i].l].pb(mp(b[i].r, i));
				else g[b[i].r].pb(mp(b[i].l, i));
			}
		}
		repn(i, 1, n) if (dfn[i] == 0) tarjan(i);
		repn(i, 1, n) sc[scc[i]].pb(i);
		repn(i, 1, m) {
			if (!cp[b[i].id]) {
				int x, y;
				if (b[i].x == 1) x = b[i].l, y = b[i].r;
				else x = b[i].r, y = b[i].l;
				if (scc[x] == scc[y]);
				else {
					du[y] += 1;
					h[scc[x]].pb(scc[y]);
					qp[y] = 1;
				}
			}
		}
		repn(i, 1, scc_cnt) {
			if (du[i] == 0) que.push(i);
		}
		ans.clear();
		while (!que.empty()) {
			int now = que.front(); que.pop();
			int st = sc[now][0];
			for (auto x: sc[now]) if (qp[x]) {
				st = x;
				break;
			}
			dfs(st);
			for (auto y: h[now]) {
				du[y]--;
				if (du[y] == 0) que.push(y);
			}
		}
		repn(i, 1, t1) ans.pb(st1[i]);
		while (t2) ans.pb(st2[t2]), t2--;
		for (auto p: ans) a[b[p].l] = b[p].x, a[b[p].r] = b[p].y;
		int res = 0;
		repn(i, 1, n) res += a[i];
		cout << res << "\n";
		rep(i, 0, ans.size()) {
			cout << ans[i];
			if (i != ans.size() - 1) cout << " ";
			else cout << "\n";
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 77292kb

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: 0
Accepted
time: 3ms
memory: 75820kb

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:

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

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 4ms
memory: 76624kb

input:

1
7 5
2 1 6 2
1 2 6 1
1 1 5 1
2 2 7 1
1 1 7 2

output:

8
3 2 1 4 5

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 8ms
memory: 75628kb

input:

1
7 6
2 1 7 2
2 1 4 2
1 2 4 1
2 1 6 1
1 1 6 2
2 2 6 1

output:

9
4 3 2 1 6 5

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 9ms
memory: 76180kb

input:

1
7 5
5 2 7 1
5 1 6 2
3 2 7 1
3 2 6 1
6 1 7 2

output:

7
1 3 5 4 2

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 4ms
memory: 76564kb

input:

1
7 6
1 2 5 1
2 1 7 2
1 2 7 1
2 2 7 1
1 1 5 2
1 2 3 1

output:

8
4 1 5 6 3 2

result:

ok Correct. (1 test case)

Test #7:

score: -100
Wrong Answer
time: 11ms
memory: 77108kb

input:

2000
15 16
2 2 3 1
12 2 15 1
3 2 9 1
6 2 14 1
2 1 15 2
5 2 6 1
7 1 10 1
9 2 15 1
2 2 3 1
4 2 12 1
2 2 9 1
5 2 8 2
3 2 13 1
12 1 13 2
9 2 13 1
5 1 14 2
15 15
5 2 11 1
1 2 8 1
8 1 15 2
6 2 8 2
8 2 9 1
1 1 6 2
6 1 9 2
2 2 5 1
2 1 10 2
7 2 10 1
1 1 15 2
5 2 15 1
7 1 11 2
1 1 2 1
5 2 9 1
15 14
3 1 5 2
1 ...

output:

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

result:

wrong answer Integer parameter [name=p_i] equals to 21, violates the range [1, 14] (test case 13)