Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Make CSP great again
- //You're as beautiful as the day I lost you
- //New year, best wishes
- #include <bits/stdc++.h>
- #define TASK "TESTCODE"
- #define Log2(x) 31 - __builtin_clz(x)
- using namespace std;
- const int N = 3e5, K = 1e6, M = 1e5, block = 550;
- int n, m, a[N + 1];
- long long dp[K + 1], add[K + 1], luck[M + 1], f[M + 1], res = 0;
- vector<int> Adj[M + 1];
- struct Trie
- {
- struct node
- {
- int child[26];
- node()
- {
- memset(child, -1, sizeof(child));
- }
- };
- vector<node> Tree;
- void new_node()
- {
- node tmp;
- Tree.push_back(tmp);
- }
- Trie()
- {
- new_node();
- }
- int Index(string &s)
- {
- int id = 0;
- for (char c : s)
- {
- int w = c - 'A';
- if (Tree[id].child[w] == -1)
- {
- Tree[id].child[w] = Tree.size();
- new_node();
- }
- id = Tree[id].child[w];
- }
- return id;
- }
- void Update(string &s, int u)
- {
- int id = 0;
- for (char c : s)
- {
- int w = c - 'A';
- add[id] = max(add[id], dp[u]);
- id = Tree[id].child[w];
- }
- }
- } Tree;
- string s[N + 1];
- void read()
- {
- cin >> n >> m;
- for (int i = 1; i <= n; ++ i)
- {
- cin >> s[i] >> a[i];
- }
- for (int i = 1; i <= m; ++ i)
- {
- int u, v;
- cin >> u >> v;
- Adj[u].push_back(v);
- Adj[v].push_back(u);
- }
- for (int i = 1; i <= M; ++ i)
- {
- sort(Adj[i].begin(), Adj[i].end(), [](const int &x, const int &y)
- {
- return Adj[x].size() > Adj[y].size();
- });
- }
- }
- long long Get(int u, long long x)
- {
- if (Adj[u].size() <= block)
- {
- long long t = luck[u];
- t = max(t, x);
- for (int v : Adj[u])
- {
- if (Adj[v].size() <= block)
- {
- break;
- }
- t = max(t, f[v]);
- }
- for (int v : Adj[u])
- {
- luck[v] = max(luck[v], t + u);
- }
- return t + u;
- }
- else
- {
- long long t = luck[u];
- t = max(t, x);
- for (int v : Adj[u])
- {
- if (Adj[v].size() <= block)
- {
- break;
- }
- luck[v] = max(luck[v], t + u);
- }
- f[u] = max(f[u], t + u);
- return t + u;
- }
- }
- void solve()
- {
- for (int i = 1; i <= n; ++ i)
- {
- int j = Tree.Index(s[i]);
- long long t = Get(a[i], add[j]);
- dp[j] = max(dp[j], t);
- res = max(res, t);
- Tree.Update(s[i], j);
- //cerr << res << '\n';
- }
- cout << res;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- if (fopen(TASK".INP", "r"))
- {
- freopen(TASK".INP", "r", stdin);
- //freopen(TASK".out", "w", stdout);
- }
- int t = 1;
- bool typetest = false;
- if (typetest)
- {
- cin >> t;
- }
- for (int __ = 1; __ <= t; ++ __)
- {
- //cout << "Case " << __ << ": ";
- read();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement