#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <utility> #include <queue> #include <vector> #include <string> #include <cstring> #define REP(a,n) for (int a = 0; a<(n); ++a) #define FOR(a,b,c) for (int a = (b); a<=(c); ++a) #define FORD(a,b,c) for (int a = (b); a>=(c); --a) #define FOREACH(a,v) for (auto a : v) #define MP make_pair #define PB push_back template<class T> inline int size2(const T&t) { return t.size(); } using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<string> vs; typedef long long LL; /////////////////////////////// #define PLUS '+' #define MIN '-' #define WCZ 'W' #define ZAP 'Z' int N; vector<pair<char, int>> prog[100000]; LL best; void symuluj(LL lg, vi gdzie, vector<LL> liczniki) { int koniec = 0; REP(a, N) while (gdzie[a] < size2(prog[a])) if (prog[a][gdzie[a]].first == PLUS) liczniki[a] += prog[a][gdzie[a]++].second; else if (prog[a][gdzie[a]].first == MIN) liczniki[a] -= prog[a][gdzie[a]++].second; else break; REP(a, N) if (gdzie[a] == size2(prog[a])) ++koniec; else if (prog[a][gdzie[a]].first == ZAP) { LL tmp = lg; lg = liczniki[a]; ++gdzie[a]; symuluj(lg, gdzie, liczniki); --gdzie[a]; lg = tmp; } else { // if (prog[a][gdzie[a]].first == WCZ) { LL tmp = liczniki[a]; liczniki[a] = lg; ++gdzie[a]; symuluj(lg, gdzie, liczniki); --gdzie[a]; liczniki[a] = tmp; } if (koniec == N) best = min(best, lg); } void solve() { cin >> N; REP(a, N) { int L; cin >> L; REP(x, L) { char c; int v; cin >> c; if (c == PLUS || c == MIN) cin >> v; prog[a].emplace_back(c, v); } while(!prog[a].empty() && prog[a].back().first != ZAP) prog[a].pop_back(); FORD(x, size2(prog[a]) - 1, 0) { if (prog[a][x].first == WCZ) { int y = x - 1; while (y >= 0 && prog[a][y].first != ZAP) prog[a][y--].first = PLUS; } } } best = 1'000'000'000'000'000'000; symuluj(0, vi(N), vector<LL>(N)); REP(a, N) prog[a].clear(); cout << best << endl; } int main() { std::ios::sync_with_stdio(false); int TT; cin >> TT; REP(tt, TT) solve(); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> #include <map> #include <utility> #include <queue> #include <vector> #include <string> #include <cstring> #define REP(a,n) for (int a = 0; a<(n); ++a) #define FOR(a,b,c) for (int a = (b); a<=(c); ++a) #define FORD(a,b,c) for (int a = (b); a>=(c); --a) #define FOREACH(a,v) for (auto a : v) #define MP make_pair #define PB push_back template<class T> inline int size2(const T&t) { return t.size(); } using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<string> vs; typedef long long LL; /////////////////////////////// #define PLUS '+' #define MIN '-' #define WCZ 'W' #define ZAP 'Z' int N; vector<pair<char, int>> prog[100000]; LL best; void symuluj(LL lg, vi gdzie, vector<LL> liczniki) { int koniec = 0; REP(a, N) while (gdzie[a] < size2(prog[a])) if (prog[a][gdzie[a]].first == PLUS) liczniki[a] += prog[a][gdzie[a]++].second; else if (prog[a][gdzie[a]].first == MIN) liczniki[a] -= prog[a][gdzie[a]++].second; else break; REP(a, N) if (gdzie[a] == size2(prog[a])) ++koniec; else if (prog[a][gdzie[a]].first == ZAP) { LL tmp = lg; lg = liczniki[a]; ++gdzie[a]; symuluj(lg, gdzie, liczniki); --gdzie[a]; lg = tmp; } else { // if (prog[a][gdzie[a]].first == WCZ) { LL tmp = liczniki[a]; liczniki[a] = lg; ++gdzie[a]; symuluj(lg, gdzie, liczniki); --gdzie[a]; liczniki[a] = tmp; } if (koniec == N) best = min(best, lg); } void solve() { cin >> N; REP(a, N) { int L; cin >> L; REP(x, L) { char c; int v; cin >> c; if (c == PLUS || c == MIN) cin >> v; prog[a].emplace_back(c, v); } while(!prog[a].empty() && prog[a].back().first != ZAP) prog[a].pop_back(); FORD(x, size2(prog[a]) - 1, 0) { if (prog[a][x].first == WCZ) { int y = x - 1; while (y >= 0 && prog[a][y].first != ZAP) prog[a][y--].first = PLUS; } } } best = 1'000'000'000'000'000'000; symuluj(0, vi(N), vector<LL>(N)); REP(a, N) prog[a].clear(); cout << best << endl; } int main() { std::ios::sync_with_stdio(false); int TT; cin >> TT; REP(tt, TT) solve(); } |