QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#112190#5673. CornholePetroTarnavskyi#WA 2ms3488kbC++171.5kb2023-06-10 15:48:022023-06-10 15:48:20

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-10 15:48:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3488kb
  • [2023-06-10 15:48:02]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

const int N = 447;
VI g[N];
string ans[N];
map<string, int> m;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	string t = "", t2 = "";
	int prev = -1;
	FOR (i, 0, SZ(s))
	{
		if (s[i] == '!')
		{
			int x = m.count(t2) ? m[t2] : SZ(m);
			m[t2] = x;
			if (prev != -1) g[prev].PB(x);
			prev = x;
			ans[x] = t;
			t = t2 = "";
		}
		else
		{
			t += s[i];
			t2 += tolower(s[i]);
		}
	}
	int x = m.count(t2) ? m[t2] : SZ(m);
	g[prev].PB(x);
	m[t2] = x;
	ans[x] = t;
	
	
	VI d(SZ(m), 100);
	VI p(SZ(m), -1);
	queue<int> q;
	q.push(0);
	d[0] = 0;
	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		
		for (auto to : g[v])
		{
			if (d[to] > d[v] + 1)
			{
				d[to] = d[v] + 1;
				q.push(to);
				p[to] = v;
			}
		}
	}
	VI path;
	while (p[x] != -1)
	{
		path.PB(x);
		x = p[x];
	}
	path.PB(x);
	reverse(ALL(path));
	FOR (i, 0, SZ(path))
	{
		if (i) cout << '!';
		cout << ans[path[i]];
	}
	cout << '\n';
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3488kb

input:

2 1
0 4

output:

2

result:

wrong answer 1st lines differ - expected: '1 3', found: '2'