fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<vector>
  3. #include <utility>
  4. #define int long long int
  5. //#define int long long 
  6. using namespace std;
  7.  
  8. struct node
  9. {
  10. 	int val;
  11. 	int dis;
  12. 	int pa;
  13. 	node* parent=nullptr;
  14. 	vector<node*> children;
  15. };
  16. int maxroot=-(int)1e9;
  17. int maxdis=-(int)1e9;
  18. node* nodelib[10001];
  19. node* creatnewnode(int tempval,int tempdis)
  20. {
  21. 	node *newnode= new node;
  22. 	newnode->val=tempval;
  23. 	newnode->dis=tempdis;
  24. 	return newnode;
  25. }
  26. int which(int a,int b)
  27. {
  28. 	if(a>b)
  29. 		return a;
  30. 	return b;
  31. }
  32. void start()
  33. {
  34. 	int tempval,tempdis,temparent;
  35. 	cin>>temparent>>tempval>>tempdis;
  36. 	if(nodelib[tempval]!=nullptr)
  37. 	{
  38. 		nodelib[tempval]->val=tempval;
  39. 		nodelib[tempval]->dis=tempdis;
  40. 		nodelib[tempval]->pa=temparent;
  41. 	}
  42. 	else
  43. 	{
  44. 		node* newnode=creatnewnode(tempval,tempdis);
  45. 		newnode->pa=temparent;
  46. 		nodelib[tempval]=newnode;
  47. 	}
  48. 	if(nodelib[temparent]!=nullptr)
  49. 	{
  50. 		nodelib[tempval]->parent=nodelib[temparent];
  51. 		nodelib[temparent]->children.emplace_back(nodelib[tempval]);
  52. 	}
  53. 	else
  54. 	{
  55. 		node *newroot=new node;
  56. 		nodelib[temparent]=newroot;
  57. 		nodelib[tempval]->parent=newroot;
  58. 		newroot->children.emplace_back(nodelib[tempval]);
  59. 	}
  60. 	return;
  61. }
  62. int bigger(int l,int f)
  63. {
  64. 	return l>f;
  65. }
  66. int check(node* root)
  67. {
  68. 	if(root==nullptr)
  69. 		return 0;
  70. 	if(root->children.size()==0)
  71. 	{
  72. 		if(root->dis > maxdis)
  73. 		{
  74. 			maxdis=root->dis;
  75. 			maxroot=root->val;
  76. 		}
  77. 		return root->dis;
  78. 	}
  79. 	vector<int> subtree;
  80. 	for(int i=0;i<root->children.size();i++)
  81. 		subtree.emplace_back(check(root->children[i]));
  82. 	sort(subtree.begin(),subtree.end(),bigger);
  83. 	if(subtree.size()>1 && subtree[0]+subtree[1]+root->dis > maxdis)
  84. 	{
  85. 		maxdis=subtree[0]+subtree[1]+root->dis;
  86. 		maxroot=root->val; 
  87. 	}
  88. 	if(subtree.size()==1 && subtree[0]+root->dis > maxdis)
  89. 	{
  90. 		maxdis=subtree[0]+root->dis;
  91. 		maxroot=root->val;
  92. 	}
  93. 	int oneside;
  94. 	if(subtree.size()==1)
  95. 		oneside=subtree[0];
  96. 	else
  97. 		oneside=which(subtree[0],subtree[1]);
  98. 	if(oneside<0)
  99. 	{
  100. 		if(root->dis>maxdis)
  101. 		{
  102. 			maxdis=root->dis;
  103. 			maxroot=root->val;
  104. 		}
  105. 		return root->dis;
  106. 	}
  107. 	else
  108. 	{
  109. 		if(root->dis+oneside>maxdis)
  110. 		{
  111. 			maxdis=root->dis+oneside;
  112. 			maxroot=root->val;
  113. 		}
  114. 		return root->dis+oneside;
  115. 	}
  116. }
  117. void initial()
  118. {
  119. 	for(int i=0;i<10001;i++)
  120.      {
  121.          //cout<<nodelib[i]<<endl;
  122.          nodelib[i]=nullptr;
  123.          //cout<<nodelib[i]<<endl;
  124.      }
  125. } 
  126. signed main()
  127. {
  128.  
  129. 	cin.tie(NULL),cout.tie(NULL);
  130.     ios::sync_with_stdio(0);
  131. 	//initial();
  132. 	int n,o;
  133. 	cin>>n>>o;
  134.  
  135. 	int tempval,tempdis,temparent;
  136. 	cin>>tempval>>tempdis;
  137. 	node *root=creatnewnode(tempval,tempdis);
  138. 	nodelib[tempval]=root;
  139. 	for(int i=0;i<n;i++)
  140. 	{
  141. 		start();
  142. 	}
  143. 	while(o--)
  144. 	{
  145. 		string command;
  146. 		cin>>command;
  147. 		if(command=="Add")
  148. 		{
  149. 			start();
  150. 		}
  151. 		else if(command=="Delete")
  152. 		{
  153.  
  154. 			int target;
  155. 			cin>>target;
  156. 			if(nodelib[target]==NULL)
  157. 				goto end;
  158. 			node *tempa=nodelib[target]->parent;
  159. 			node *tempdelete=nodelib[target];
  160. 			for(int i=0;i<tempa->children.size();i++)
  161. 			{
  162. 				if(tempdelete==tempa->children[i])
  163. 				{
  164.  
  165. 					tempa->children.erase(tempa->children.begin()+i);
  166. 					break;	
  167. 				}	
  168. 			} 
  169.  
  170. 			if(tempdelete->children.size()!=0)
  171. 			{
  172.  
  173. 				for(int i=0;i<tempdelete->children.size();i++)
  174. 				{
  175. 					tempdelete->children[i]->parent=tempa;
  176. 					tempdelete->children[i]->pa=tempa->val;
  177. 					tempa->children.emplace_back(tempdelete->children[i]);
  178. 				}
  179. 			}
  180. 			/*for(auto i=tempa->children.begin();i!=tempa->children.end();i++)
  181. 				cout<<(*i)->val<<", ";
  182. 			cout<<endl;
  183. 				 */
  184. 			nodelib[target]=nullptr;
  185. 			delete tempdelete; 
  186.  
  187. 		}
  188. 		else if(command=="Check")
  189. 		{
  190. 			check(root);
  191. 			cout<<"Maximum Value: "<<maxdis<<endl;
  192. 			cout<<"Root of the Path: "<<maxroot<<endl;
  193. 			maxdis=-(int)1e9;
  194. 		}
  195. 	end:;	
  196. 	}
  197. 	check(root);
  198. 	cout<<"Final Root: "<<maxroot<<endl;
  199.  }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
4 3
0 -30
0 1 7
2 3 2
2 4 13
0 2 19
Check
Add 0 5 10
Delete 2
stdout
copy 
Maximum Value: 34
Root of the Path: 2
Final Root: 4
https://ideone.com/Awm29y
language:
C++14 (gcc 8.3)
created:
17 days 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!