fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<string.h>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<map>
  10. #include<set>
  11. #include<cstring>
  12. #include<cstdlib>
  13. #include<iomanip>
  14. #include<climits>
  15. #include<cstdio>
  16. using namespace std;
  17. #define inf 2147483647//2^31   
  18. #define ll 9223372036854775807//2^64
  19. #define maxn 30000
  20. struct bign
  21. {
  22.     int len, s[maxn];
  23.  
  24.     bign()
  25.     {
  26.         memset(s, 0, sizeof(s));
  27.         len = 1;
  28.     }
  29.  
  30.     bign(int num)
  31.     {
  32.         *this = num;
  33.     }
  34.  
  35.     bign(const char* num) 
  36.     {
  37.         *this = num;
  38.     }
  39.  
  40.     bign operator = (int num) 
  41.     {
  42.         char s[maxn];
  43.         sprintf(s, "%d", num);
  44.         *this = s;
  45.         return *this;
  46.     }
  47.  
  48.     bign operator = (const char* num) 
  49.     {
  50.         len = strlen(num);
  51.         for (int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
  52.         return *this;
  53.     }
  54.  
  55.     string str() const 
  56.     {
  57.         string res = "";
  58.         for (int i = 0; i < len; i++) res = (char)(s[i] + '0') + res;
  59.         if (res == "") res = "0";
  60.         return res;
  61.     }
  62.  
  63.     bign operator + (const bign& b) const
  64.     {
  65.         bign c;
  66.         c.len = 0;
  67.         for (int i = 0, g = 0; g || i < max(len, b.len); i++) 
  68.         {
  69.             int x = g;
  70.             if (i < len) x += s[i];
  71.             if (i < b.len) x += b.s[i];
  72.             c.s[c.len++] = x % 10;
  73.             g = x / 10;
  74.         }
  75.         return c;
  76.     }
  77.  
  78.     void clean() 
  79.     {
  80.         while(len > 1 && !s[len-1]) len--;
  81.     }
  82.  
  83.     bign operator * (const bign& b) 
  84.     {
  85.         bign c; c.len = len + b.len;
  86.         for (int i = 0; i < len; i++)
  87.         for (int j = 0; j < b.len; j++)
  88.         c.s[i+j] += s[i] * b.s[j];
  89.         for (int i = 0; i < c.len-1; i++)
  90.         {
  91.             c.s[i+1] += c.s[i] / 10;
  92.             c.s[i] %= 10;
  93.         }
  94.         c.clean();
  95.         return c;
  96.     }
  97.  
  98.     bign operator - (const bign& b) 
  99.     {
  100.         bign c; c.len = 0;
  101.         for (int i = 0, g = 0; i < len; i++) 
  102.         {
  103.             int x = s[i] - g;
  104.             if (i < b.len) x -= b.s[i];
  105.             if (x >= 0) 
  106.                 g = 0;
  107.             else 
  108.             {
  109.                 g = 1;
  110.                 x += 10;
  111.             }
  112.             c.s[c.len++] = x;
  113.         }
  114.         c.clean();
  115.         return c;
  116.     }
  117.  
  118.     bool operator < (const bign& b) const
  119.     {
  120.         if (len != b.len) return len < b.len;
  121.         for (int i = len-1; i >= 0; i--)
  122.         if (s[i] != b.s[i]) return s[i] < b.s[i];
  123.         return false;
  124.     }
  125.  
  126.     bool operator > (const bign& b) const
  127.     {
  128.         return b < *this;
  129.     }
  130.  
  131.     bool operator <= (const bign& b) 
  132.     {
  133.         return !(b > *this);
  134.     }
  135.  
  136.     bool operator == (const bign& b) 
  137.     {
  138.         return !(b < *this) && !(*this < b);
  139.     }
  140.  
  141.     bool operator != (const bign& b) 
  142.     {
  143.         return (b < *this) || (*this < b);
  144.     }
  145.  
  146.     bign operator += (const bign& b) 
  147.     {
  148.         *this = *this + b;
  149.         return *this;
  150.     }
  151. };
  152. istream& operator >> (istream &in, bign& x) 
  153. {
  154.     string s;
  155.     in >> s;
  156.     x = s.c_str();
  157.     return in;
  158. }
  159. ostream& operator << (ostream &out, const bign& x) 
  160. {
  161.     out << x.str();
  162.     return out;
  163. }
  164. string now[10240]={};
  165. string goal[12040]={};
  166. vector<int>tree[12040]={};
  167. int k;
  168. void build(int l,int r,int root){
  169. 	if(k<0||l>r){
  170. 	return;
  171. 	}
  172. 	string x=goal[k];
  173. 	for(int i=l;i<=r;i++){
  174. 		if(now[i]==x){
  175. 			if(root==0){
  176. 				int sum=0;
  177. 				for(int j=0;j<x.size();j++){
  178. 				sum=sum*10+x[j]-'0';
  179. 				}
  180. 			}
  181. 			else{
  182. 				int sum=0;
  183. 				for(int j=0;j<x.size();j++){
  184. 				sum=sum*10+x[j]-'0';
  185. 				}
  186. 				tree[root].push_back(sum);
  187. 			}
  188. 				int sun=0;
  189. 				for(int j=0;j<x.size();j++){
  190. 				sun=sun*10+x[j]-'0';
  191. 				}
  192. 				k--;
  193. 		build(i+1,r,sun);
  194. 		build(l,i-1,sun);
  195. 		break;
  196. 		}
  197. 	}
  198. }
  199. int maxr=inf;
  200. int ans=inf;
  201. void dfs(int root,int sum){
  202. 	if(tree[root].size()==0){
  203. 		if(sum<maxr){
  204. 		maxr=sum;
  205. 		ans=root;
  206. 		}
  207. 		else if(sum==maxr){
  208. 			if(ans>root){
  209. 			ans=root;
  210. 			}
  211. 		}
  212. 	}
  213. 	for(int i=0;i<tree[root].size();i++){
  214. 	dfs(tree[root][i],sum+tree[root][i]);
  215. 	}
  216. }
  217. int main()
  218. {
  219. string a;
  220. while(cin>>a){
  221. 	maxr=inf;
  222. 	ans=inf;
  223. 	for(int i=0;i<12040;i++){
  224. 		tree[i].clear();
  225. 	}
  226. 	memset(now,0,sizeof(now));
  227. 	memset(goal,0,sizeof(goal));
  228. 	int i=0;
  229. 	now[i]=a;
  230. 	i++;
  231. 	if(cin.peek()!='\n'){
  232. 	while(1){
  233. 	cin>>a;
  234. 	now[i]=a;
  235. 	i++;
  236. 	if(cin.peek()=='\n'){
  237. 	break;
  238. 	}
  239. 	}
  240. 	}
  241. 	int q=0;
  242. 	while(1){
  243. 	string x;
  244. 	cin>>x;
  245. 	goal[q]=x;
  246. 	q++;
  247. 	if(cin.peek()=='\n'){
  248. 	break;
  249. 	}
  250. 	}
  251. 	k=q-1;
  252. 	build(0,q-1,0);
  253. 	int sun=0;
  254. 	for(int f=0;f<goal[q-1].size();f++){
  255. 	sun=sun*10+goal[q-1][f]-'0';
  256. 	}
  257. 	dfs(sun,0);
  258. 	cout<<ans<<endl;
  259. }
  260. 	return 0;
  261. }
Runtime error #stdin #stdout 0s 3692KB
comments (?)
stdin
copy 
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
stdout
copy 
Standard output is empty
https://ideone.com/r2xFe1
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!