QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#522307#6601. Mean Streets of GadgetzanzhangbojuWA 10ms54888kbC++171.8kb2024-08-16 21:09:002024-08-16 21:09:00

Judging History

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

  • [2024-08-16 21:09:00]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:54888kb
  • [2024-08-16 21:09:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e6 + 5;
int n, m;
int deg[N];
vector<int> g[N];
string s;
void NO() {
	cout << "conflict\n";
	exit(0);
}
int ans[N];
int id[N];
queue<int> Q;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	getline(cin, s);
	for (int i = 1; i <= n; i++)
		ans[i] = -1;
	int idx = n;
	while (m--) {
		getline(cin, s);
		if (s.find('>') == s.npos) {
			int res = 0;
			int i = (s[0] == '!');
			while (i < s.size() && isdigit(s[i]))
				res = res * 10 + (s[i] - '0'), i++;
			if (ans[res] != -1 && ans[res] != (s[0] != '!'))
				NO();
			ans[res] = (s[0] != '!');
		}
		else {
			int i = 0;
			vector<int> ve;
			while (1) {
				int res = 0;
				while (i < s.size() && isdigit(s[i]))
					res = res * 10 + (s[i] - '0'), i++;
				ve.push_back(res);
				if (s[i + 1] == '-') {
			 		i += 4;
					break;	
				}
				i++;
			}
			bool flag = 0;
			if (s[i] == '!') {
				flag = 1;
				i++;
			}
			int x = 0;
			while (i < s.size() && isdigit(s[i]))
				x = x * 10 + (s[i] - '0'), i++;
			// cout << "test " << x << " " << flag << endl;
			id[++idx] = x * (flag ? -1 : 1);
			deg[idx] = ve.size();
			for (int u : ve) g[u].push_back(idx);
		}
	}
	for (int i = 1; i <= n; i++)
		if (ans[i] == 1) 
			Q.push(i);
	for (int i = 1; i <= n; i++)
		id[i] = i;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		int t = abs(id[u]);
		if (ans[t] != -1 && ans[t] != (id[u] > 0)) NO();
		if (ans[t] != -1) continue;
		ans[t] = (id[u] > 0);
		if (id[u] < 0) continue;
		for (int v : g[t]) {
			--deg[v];
			// cout << "fsfsjfhs " << u << " " << t << " " << v << " " << id[v] << " " << deg[v] << endl;
			if (!deg[v]) Q.push(v);
		}
	}
	for (int i = 1; i <= n; i++)
		cout << (ans[i] == 1 ? 'T' : 'F');
	cout << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 54888kb

input:

3 3
!1
2 -> 1
1 2 -> !3

output:

FFF

result:

ok ok, solution exists

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 54888kb

input:

6 4
1 -> 2
1 3 -> !2
1 -> 3
4 -> 2
1
2 3 4 -> !1

output:

TFFF

result:

wrong answer participant found wrong solution