QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511258#3401. Assembling ServicesPetroTarnavskyi#AC ✓56ms3732kbC++202.2kb2024-08-09 18:07:162024-08-09 18:07:17

Judging History

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

  • [2024-08-09 18:07:17]
  • 评测
  • 测评结果:AC
  • 用时:56ms
  • 内存:3732kb
  • [2024-08-09 18:07:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int INF = 1e9;

template<typename T>
void updMin(T& a, T b)
{
	a = min(a, b);
}

template<typename T>
void updMax(T& a, T b)
{
	a = max(a, b);
}

int n, m, o;

string dfs(int v, const vector<VI>& g)
{
	string cur = "P" + to_string(v + 1);
	if (g[v].empty())
		return cur;
	string res = "(" + cur + "(";
	for (int to : g[v])
		res += dfs(to, g) + "|";
	res.back() = ')';
	res += ")";
	return res;
}

void solve()
{
	string s;
	cin >> s;
	VI tExec(n);
	vector<VI> in(n), out(n);
	FOR(i, 0, n)
	{
		cin >> tExec[i];
		int cntIn, cntOut;
		cin >> cntIn;
		FOR(j, 0, cntIn)
		{
			int x;
			cin >> x;
			x--;
			in[i].PB(x);
		}
		cin >> cntOut;
		FOR(j, 0, cntOut)
		{
			int x;
			cin >> x;
			x--;
			out[i].PB(x);
		}
	}
	VI tVar(m), f(m, -1), tProg(n, INF), par(n, -1);
	FOR(i, 0, m)
	{
		tVar[i] = s[i] == '1' ? 0 : INF;
	}
	FOR(it, 0, n + 7)
	{
		FOR(i, 0, n)
		{
			tProg[i] = 0;
			for (int x : in[i])
			{
				if (tVar[x] > tProg[i])
				{
					tProg[i] = tVar[x];
					par[i] = f[x];
				}
			}
		}
		FOR(i, 0, n)
		{
			for (int x : out[i])
			{
				int cur = tProg[i] + tExec[i];
				if (cur < tVar[x])
				{
					tVar[x] = cur;
					f[x] = i;
				}
			}
		}
	}
	if (tVar[o] == INF)
	{
		cout << "-1\n\n";
		return;
	}
	vector<VI> g(n);
	FOR(i, 0, n)
	{
		if (par[i] != -1 && tProg[i] < tVar[o])
			g[par[i]].PB(i);
	}
	string ans = "(";
	FOR(i, 0, n)
	{
		if (tProg[i] == 0)
		{
			ans += dfs(i, g) + "|";
		}
	}
	ans.back() = ')';
	assert(SZ(ans) > 1);
	cout << tVar[o] << " " << ans << "\n\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int tc = 1; ; tc++)
	{
		cin >> n >> m >> o;
		if (n == 0 && m == 0 && o == 0)
			break;
		cout << "Case " << tc << ": ";
		o--;
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 56ms
memory: 3732kb

input:

42 6 6
100010
46 2 1 1 3 4 5 5
22 2 1 1 4 5 6 2 2
95 4 4 4 4 4 2 6 5
48 5 5 4 4 2 6 4 2 5 5 6
91 3 1 5 5 3 5 5 3
6 1 4 5 3 1 4 4 3
30 4 1 5 1 3 5 3 6 5 1 4
27 4 6 5 3 1 4 6 4 6 2
59 5 1 4 3 6 1 6 6 3 5 1 4 6
74 3 1 5 1 6 1 6 6 4 5 6
53 1 5 4 5 5 5 4
92 3 4 2 6 4 4 6 6 2
59 2 1 3 5 3 5 4 3 1
92 3 6 5...

output:

Case 1: 22 (P1|P2|P5|P10|P11|P21)

Case 2: 53 ((P1(P6|P19|(P50(P58|P100|P114|P144|P158|P186))))|P2|(P3(P31|P127|P180))|(P4(P32|(P40(P80|P104|P126|P139|P200))|P170))|P5|(P7(P33|P187))|(P8(P36))|P10|P11|P12|P13|(P14(P49|P69|P121|P145))|P15|P16|(P18(P181|P204))|(P20(P21|(P146(P208))|P201))|P23|(P24(P15...

result:

ok  (100 test cases)