fork download
copy 
  1. /// Day Created: mar 31st 2026
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. #define fname ""
  7. #define ll long long
  8. // 548
  9. using namespace std;
  10. int n, m;
  11. int p[300005];
  12. string s[300005];
  13. vector<int> edge[100005], heavy[100005];
  14. ll dp[300005], g[300005];
  15.  
  16. struct node {
  17. 	node *child[26];
  18. 	ll res;
  19. 	node() {
  20. 		res=0;
  21. 		for(int i=0; i<26; ++i) child[i]=NULL;
  22. 	}
  23. } *root=new node();
  24.  
  25. void update(string x, const ll &val) {
  26. 	node *cur=root;
  27. 	for(int i=0; i<x.size(); ++i) {
  28. 		if(cur->child[x[i]-97]==NULL) cur->child[x[i]-97]=new node();
  29. 		cur=cur->child[x[i]-97];
  30. 	}
  31. 	cur->res=max(cur->res, val);
  32. }
  33.  
  34. ll get(string x) {
  35. 	ll res=0;
  36. 	node *cur=root;
  37. 	for(int i=0; i<(int)x.size()-1; ++i) {
  38. 		cur=cur->child[x[i]-97];
  39. 		res=max(res, cur->res);
  40. 	}
  41. 	return res;
  42. }
  43.  
  44. void solve() {
  45. 	cin>>n>>m;
  46. 	for(int i=1; i<=n; ++i) {
  47. 		cin>>s[i]>>p[i];
  48. 	}
  49. 	for(int i=1; i<=m; ++i) {
  50. 		int u, v;
  51. 		cin>>u>>v;
  52. 		edge[u].emplace_back(v), edge[v].emplace_back(u);
  53. 	}
  54.  
  55. 	// find heavy/light node
  56. 	for(int i=1; i<=100000; ++i) 
  57. 		if((int)edge[i].size()>548) 
  58. 			for(const auto &v:edge[i]) 
  59. 				heavy[v].emplace_back(i);
  60.  
  61. 	// answer
  62. 	fill(dp+1, dp+n+1, -1e18), fill(g+1, g+n+1, -1e18);
  63. 	for(int i=n; i; --i) {
  64. 		dp[i]=0;
  65. 		// case 1
  66. 		dp[i]=get(s[i])+p[i];
  67. 		// case 2
  68. 		for(const auto &v:heavy[p[i]]) dp[i]=max(dp[i], g[v]+p[i]);
  69. 		if((int)edge[p[i]].size()<=548) 
  70. 			for(const auto &light:edge[i]) dp[i]=max(dp[i], g[light]+p[i]);
  71. 	}
  72. 	cout<<*max_element(dp+1, dp+n+1);
  73. }
  74.  
  75. main() {
  76. 	if(fopen(fname".inp", "r")) {
  77. 		freopen(fname".inp", "r", stdin);
  78. 		freopen(fname".out", "w", stdout);
  79. 	}
  80. 	cin.tie(0)->sync_with_stdio(0);
  81. 	int tc=1;
  82. 	// cin>>tc;
  83. 	while(tc--) {
  84. 		solve();
  85. 		// cout<<'\n';
  86. 	}
  87. }
Success #stdin #stdout 0.01s 19872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JigUof
language:
C++ (gcc 8.3)
created:
5 hours 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!