zoj 2367 PL/Cool

#include <functional>#include <algorithm>#include <iostream>#include <iomanip>#include <numeric>#include <sstream>#include <cstring>#include <cstdio>#include <string>#include <vector>#include <bitset>#include <queue>#include <cmath>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define REP(i, n) for (int i=0;i<int(n);++i)#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)#define REP_1(i, n) for (int i=1;i<=int(n);++i)#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)#define REP_N(i, n) for (i=0;i<int(n);++i)#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)#define REP_1_N(i, n) for (i=1;i<=int(n);++i)#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)#define DO(n) while(n--)#define DO_C(n) int n____ = n; while(n____--)#define _TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a+s_;i!=b_;i+=s_)#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)#define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j)#define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j)#define REP_2(i, j, n, m) REP(i, n) REP(j, m)#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)#define ALL(A) A.begin(), A.end()#define LLA(A) A.rbegin(), A.rend()#define CPY(A, B) memcpy(A, B, sizeof(A))#define INS(A, P, B) A.insert(A.begin() + P, B)#define ERS(A, P) A.erase(A.begin() + P)#define BSC(A, X) fP(ALL(A), X) // != A.end()#define CTN(T, x) (T.fP(x) != T.end())#define SZ(A) int(A.size())#define PB push_back#define MP(A, B) make_pair(A, B)#define Rush int T____; RD(T____); DO(T____)#define Display(A, n, m) { REP(i, n){  REP(j, m) cout << A[i][j] << " ";cout << endl;}}#define Display_1(A, n, m) {REP_1(i, n){ REP_1(j, m) cout << A[i][j] << " ";cout << endl;}}#pragma comment(linker, "/STACK:36777216")typedef long long LL;typedef double DB;typedef unsigned UINT;typedef unsigned long long ULL;typedef vector<int> VI;typedef vector<char> VC;typedef vector<string> VS;typedef vector<LL> VL;typedef vector<DB> VD;typedef set<int> SI;typedef set<string> SS;typedef set<LL> SL;typedef set<DB> SD;typedef map<int, int> MII;typedef map<string, int> MSI;typedef map<LL, int> MLI;typedef map<DB, int> MDI;typedef map<int, bool> MIB;typedef map<string, bool> MSB;typedef map<LL, bool> MLB;typedef map<DB, bool> MDB;typedef pair<int, int> PII;typedef pair<int, bool> PIB;typedef vector<PII> VII;typedef vector<VI> VVI;typedef vector<VII> VVII;typedef set<PII> SII;typedef map<PII, int> MPIII;typedef map<PII, bool> MPIIB;template<class T> inline void RD(T &);template<class T> inline void OT(const T &);inline int RD(){ int x; RD(x); return x;}template<class T> inline T& _RD(T &x){ RD(x); return x;}inline void RC(char &c){scanf(" %c", &c);}inline char RC(){ char x; RC(x); return x;}inline void RS(char *s){scanf("%s", s);}template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}template<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);}template<class T0, class T1, class T2, class T3, class T4> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);}template<class T0, class T1> inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);}template<class T0, class T1, class T2> inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);}template<class T0, class T1, class T2, class T3> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}template<class T0, class T1, class T2, class T3, class T4> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){ while (!Q.empty()) Q.pop();}template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){ while (!Q.empty()) Q.pop();}template<class T> inline void CLR(T &A){A.clear();}template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2){FLC(A0), FLC(A1), FLC(A2);}template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3){FLC(A0), FLC(A1), FLC(A2), FLC(A3);}template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);}template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);}template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);}template<class T> inline void SRT(T &A){sort(ALL(A));}template<class T, class C> inline void SRT(T &A, C B){sort(ALL(A), B);}const int MOD = 1000000007;const int INF = 0x3f3f3f3f;const LL INF_64 = 0x3f3f3f3f3f3f3f3fLL;const DB EPS = 1e-9;const DB OO = 1e10;const DB PI = acos(-1.0); //PI = 3.14159265358979323846264; template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;}template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}template<class T> inline T max(T a, T b, T c, T d){return max(min(a, b), max(c, d));}template<class T> inline T sqr(T a){return a*a;}template<class T> inline T cub(T a){return a*a*a;}int Ceil(int x, int y){return (x - 1) / y + 1;}inline bool _1(int x, int i){return x & 1<<i;}inline bool _1(LL x, int i){return x & 1LL<<i;}inline LL _1(int i){return 1LL<<i;}inline LL _U(int i){return _1(i) - 1;};template<class T> inline T low_bit(T x) { return x & -x;}template<class T> inline T high_bit(T x) { T p = low_bit(x); while (p != x) x -= p, p = low_bit(x); return p;}template<class T> inline T cover_bit(T x){ T p = 1; while (p < x) p <<= 1; return p;}inline int count_bits(int x){ x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8); x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16); return x;}inline int count_bits(LL x){ x = (x & 0x5555555555555555LL) + ((x & 0xaaaaaaaaaaaaaaaaLL) >> 1); x = (x & 0x3333333333333333LL) + ((x & 0xccccccccccccccccLL) >> 2); x = (x & 0x0f0f0f0f0f0f0f0fLL) + ((x & 0xf0f0f0f0f0f0f0f0LL) >> 4); x = (x & 0x00ff00ff00ff00ffLL) + ((x & 0xff00ff00ff00ff00LL) >> 8); x = (x & 0x0000ffff0000ffffLL) + ((x & 0xffff0000ffff0000LL) >> 16); x = (x & 0x00000000ffffffffLL) + ((x & 0xffffffff00000000LL) >> 32); return x;}int reverse_bits(int x){ x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa); x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc); x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0); x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00); x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000); return x;}LL reverse_bits(LL x){ x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL); x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL); x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL); x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL); x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL); x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL); return x;}template<class T> inline void RD(T &x){ char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}template<class T> inline void OT(const T &x){ printf("%dn", x);}const int N = 30009, L = 209;const int AddOpt = -INF + 3; // +const int SubOpt = -INF + 4; // -const int MulOpt = -INF + 6; // *const int DivOpt = -INF + 7; // /const int ModOpt = -INF + 8; // %const int RisOpt = -INF + 9; // ^const int LeftBracket = -INF + 12; // (const int RightBracket = -INF + 13; // )inline int level(int x){ if (x > RightBracket) return 0; return (x-(-INF))/3;}inline int sgn(int x){ return x < 0 ? -1 : x > 0;}MSI H; string S[N];int P[N], R[N]; int n, tot;inline int Find(int x){ if (P[x] != x) P[x] = Find(P[x]); return P[x];}inline void Union(int x, int y){ x = Find(x), y = Find(y); if (x == y) return; if (R[x] < R[y]) P[y] = x; else { if (R[x] == R[y]) ++R[x]; P[x] = y; }}inline int pow(int a , int b){ int c = 1; while (b) { if (b&1) c *= a; a *= a, b >>= 1; } return c;}inline int stoi(string s){ int ans = 0; REP_C(i, SZ(s)) ans = (ans * 10 + s[i] - '0'); return ans;}inline int Insert(string s){ H[s] = ++tot, S[tot] = s; P[tot] = tot, R[tot] = 0; return tot;}int sta[L], tmp[L]; int _calc(int l, int r){ int n = 0, _n; FOR(i, l, r){ tmp[++n] = sta[i]; while(n>=2 && !level(tmp[n]) && level(tmp[n-1]) == 1 && ((n==2)||(level(tmp[n-2])))) tmp[--n] = tmp[n] == AddOpt ? tmp[n+1] : -tmp[n+1]; } reverse(tmp+1, tmp+n+1); _n = n, n = 0; REP_1(i, _n){ tmp[++n] = tmp[i]; if(n>=3 && tmp[n-1] == RisOpt) tmp[n-=2] = pow(tmp[n+2] , tmp[n]); } reverse(tmp+1, tmp+n+1); _n = n, n = 0; REP_1(i, _n){ tmp[++n] = tmp[i]; if (n>=3 && level(tmp[n-1])==2){ n-=2; if(tmp[n+1] == MulOpt) tmp[n] = tmp[n] * tmp[n+2]; else if(tmp[n+1] == DivOpt) tmp[n] = tmp[n] / tmp[n+2]; else tmp[n] = tmp[n] % tmp[n+2] * sgn(tmp[n+2]); } } _n = n, n = 0; REP_1(i, _n){ tmp[++n] = tmp[i]; if(n>=3 && level(tmp[n-1])==1){ n-=2; if(tmp[n+1] == AddOpt) tmp[n] = tmp[n] + tmp[n+2]; else tmp[n] = tmp[n] - tmp[n+2]; } } return tmp[1];}int calc(){ int top = -1; REP(i, n){ sta[++top] = sta[i]; if(sta[top] == RightBracket){ int j=top-1; while (sta[j]!=LeftBracket) --j; sta[j] = _calc(j+1, top), top = j; } } return sta[0];}#define gc getcharvoid prep(){ char buf[300], ch; int len = 0; while(scanf("%c", &ch) != EOF){ if(ch == 'n') break; if(ch != ' ') buf[len++] = tolower(ch); } sta[0] = LeftBracket, n = 1; REP(i, len){ switch(buf[i]){ case '(': sta[n] = LeftBracket; break; case ')': sta[n] = RightBracket; break; case '+': sta[n] = AddOpt; break; case '-': sta[n] = SubOpt; break; case '*': sta[n] = MulOpt; break; case '/': sta[n] = DivOpt; break; case '%': sta[n] = ModOpt; break; case '^': sta[n] = RisOpt; break; default: string s = string(1, buf[i++]); while( (i<len)&& isalnum(buf[i])) s.PB(buf[i++]); int x = H[s]; if(!x) sta[n] = isalpha(s[0]) ? 0 : stoi(s); else x = Find(x), sta[n] = isalpha(S[x][0]) ? 0 : stoi(S[x]); --i; } ++n; } sta[n++] = RightBracket;}void defi(){ string s1, s2; cin >> s1 >> s2; gc(); int x = H[s1], y = H[s2]; if (x && P[x] != x) return;  if (x && y && Find(y) == x) return;  if(!x) x = Insert(s1); if(!y) y = Insert(s2); Union(x, y);}int main(){ Rush{ CLR(H); tot = 0; scanf("nn"); char ch; while(true){ ch = gc(); if((ch!='p')&&(ch!='d')) break; if( ch == 'd' ) gc(),gc(),gc(),gc(),gc(), defi(); else gc(),gc(),gc(),gc(), prep(), OT(calc()); } if (T____) puts(""); }}