SHARE
TWEET

Untitled

a guest Feb 17th, 2020 131 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
  4. #define int long long
  5. #define pb push_back
  6. #define pii pair<signed,signed>
  7. #define ff first
  8. #define ss second
  9. #define max(a,b) a>b?a:b
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12.  
  13. const int MAXN = 1200000;
  14. int t, n, m;
  15. bool tf;
  16. int cnt, tmp, ans;
  17. int s1, t1, s2, t2;
  18. int a, b;
  19. vector <int> len;
  20. vector <int> dis;
  21. vector <signed> deg;
  22. vector <bool> vis;
  23. vector <vector<signed>> v;
  24. cc_hash_table <int,signed> id;
  25. vector <vector<pii>> path;
  26.  
  27. inline char readchar() {
  28.     static const size_t bufsize = 65536;
  29.     static char buf[bufsize];
  30.     static char *p = buf, *end = buf;
  31.     if (p == end) end = buf + fread_unlocked(buf, 1, bufsize, stdin), p = buf;
  32.     return *p++;
  33. }
  34.  
  35. inline void const Read(int & p) {
  36.     p = 0;
  37.     //int tmp = 0;
  38.     char c = readchar();
  39.     //tmp = !(c^'-');
  40.     while (c < '0' || c > '9') {
  41.         c = readchar();
  42.     }
  43.     while (c >= '0' && c <= '9')
  44.         p = (p<<3)+(p<<1)+(c^48), c = readchar();
  45.     //p = tmp?-p:p;
  46. }
  47.  
  48. inline int h(pii a) {
  49.     return a.ff * MAXN + a.ss;
  50. }
  51.  
  52. inline void init() {
  53.     ans = cnt = tf = 0;
  54.     len.clear(), len.resize(n+1);
  55.     id.clear();
  56.     v.clear(), v.resize(n+1);
  57. }
  58.  
  59. inline void init2() {
  60.     path.clear(), path.resize(2*(n+m)+1);
  61.     deg.clear(), deg.resize(2*(n+m)+1);
  62.     dis.clear(), dis.resize(2*(n+m)+1);
  63.     vis.clear(), vis.resize(2*(n+m)+1);
  64. }
  65.  
  66. void DFS(int now) {
  67.     vis[now] = 1;
  68.     for (pii e : path[now]) {
  69.         deg[e.ff]--;
  70.         dis[e.ff] = max(dis[e.ff], dis[now] + e.ss);
  71.         if (!deg[e.ff]) DFS(e.ff);
  72.     }
  73. }
  74.  
  75. signed main() {
  76.     //ios_base::sync_with_stdio(0), cin.tie(0);
  77.     Read(t);
  78.     while (t--) {
  79.         Read(n), Read(m);
  80.         init();
  81.         for (int i = 1; i <= n; i++) {
  82.             Read(len[i]);
  83.             v[i].pb(0);
  84.             id[h(pii(i, 0))] = ++cnt;
  85.             v[i].pb(len[i]);
  86.             id[h(pii(i, len[i]))] = ++cnt;
  87.         }
  88.         init2();
  89.         for (int i = 0; i < m; i++) {
  90.             Read(s1), Read(t1);
  91.             Read(s2), Read(t2);
  92.             a = h(pii(s1, t1));
  93.             b = h(pii(s2, t2));
  94.             if (!id[a]) {
  95.                 v[s1].pb(t1);
  96.                 id[a] = ++cnt;
  97.             }
  98.             if (!id[b]) {
  99.                 v[s2].pb(t2);
  100.                 id[b] = ++cnt;
  101.             }
  102.             path[id[a]].pb(pii(id[b], 1));
  103.             deg[id[b]]++;
  104.         }
  105.         for (int i = 1; i <= n; i++) {
  106.             sort(v[i].begin(), v[i].end());
  107.             tmp = 0;
  108.             for (int j : v[i]) {
  109.                 if (!j) continue;
  110.                 path[id[h(pii(i, tmp))]].pb(pii(id[h(pii(i, j))], j-tmp));
  111.                 deg[id[h(pii(i, j))]]++;
  112.                 tmp = j;
  113.             }
  114.         }
  115.         for (int i = 0; i < n; i++)
  116.             DFS(i*2+1);
  117.         for (int i = 1; i <= id.size() && !tf; i++) {
  118.             if (deg[i] > 0)
  119.                 cout << "LoveLive!\n", tf = 1;
  120.             ans = max(ans, dis[i]);
  121.         }
  122.         if (!tf) cout << ans << "\n";
  123.     }
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top