QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511258 | #3401. Assembling Services | PetroTarnavskyi# | AC ✓ | 56ms | 3732kb | C++20 | 2.2kb | 2024-08-09 18:07:16 | 2024-08-09 18:07:17 |
Judging History
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)