SHARE
TWEET

Untitled

a guest Nov 14th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define F first
  6. #define S second
  7. #define ld long double
  8. #define ll long long
  9. #define TIME 1.0*clock()/CLOCKS_PER_SEC
  10. #define endl '\n'
  11.  
  12. mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
  13.  
  14. const int N = 3e5 + 10;
  15. const ll MOD = 1e9 + 7;
  16. const int rx[4] = {-1, 0, 1, 0};
  17. const int ry[4] = {0, 1, 0, -1};
  18. const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  19. const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  20. const int hx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
  21. const int hy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
  22. const ld eps = 1e-7;
  23. const double pi = acos(-1.0);
  24. const int INF = 1e9;
  25.  
  26. vector <vector <int> > pm;
  27. vector <int> g[N];
  28. bool used[N];
  29. int sz[N], kol[N], n, k, ans = INF;
  30.  
  31. struct segtree {
  32.     vector <int> t;
  33.     int nw;
  34.  
  35.     segtree (int n) {
  36.         nw = (1 << (32 - __builtin_clz(n) - (__builtin_popcount(n) == 1)));
  37.         t.resize(nw << 1, INF);
  38.     }
  39.  
  40.     void modify(int v, int cl, int cr, int pos, int val) {
  41.         if (cr - cl == 1) {
  42.             t[v] = min(t[v], val);
  43.             return;
  44.         }
  45.         int mid = (cl + cr) / 2;
  46.         if (pos < mid) modify(v * 2, cl, mid, pos, val);
  47.         else modify(v * 2 + 1, mid, cr, pos, val);
  48.         t[v] = min(t[v * 2], t[v * 2 + 1]);
  49.     }
  50.  
  51.     void modify(int pos, int val) {
  52.         modify(1, 1, nw + 1, pos, val);
  53.     }
  54.  
  55.     int mn(int v, int cl, int cr, int l, int r) {
  56.         if (cl >= l && cr <= r) return t[v];
  57.         if (cl >= r || cr <= l) return INF;
  58.         int mid = (cl + cr) / 2;
  59.         return min(mn(v * 2, cl, mid, l, r), mn(v * 2 + 1, mid, cr, l, r));
  60.     }
  61.  
  62.     int mn(int l, int r) {
  63.         return mn(1, 1, nw + 1, l, r + 1);
  64.     }
  65. };
  66.  
  67. void calc_sz(int v, int p = -1) {
  68.     sz[v] = 1;
  69.     for (auto to : g[v]) {
  70.         if (to == p || used[to]) continue;
  71.         calc_sz(to, v);
  72.         sz[v] += sz[to];
  73.     }
  74. }
  75.  
  76. void dfs(int v, int p, int deep, segtree &sgt1, segtree &sgt2) {
  77.     int mn = INF;
  78.     for (int i = 0; i < k; i++) {
  79.         mn = min(mn, sgt1.mn(1, pm[v * 2][i] - 1));
  80.         mn = min(mn, sgt2.mn(pm[v * 2 + 1][i] + 1, sgt2.nw));
  81.     }
  82.     ans = min(ans, mn + deep);
  83.     for (auto to : g[v]) {
  84.         if (to == p || used[to]) continue;
  85.         dfs(to, v, deep + 1, sgt1, sgt2);
  86.     }
  87.     for (int i = 0; i < k; i++) {
  88.         sgt1.modify(pm[v * 2 + 1][i], deep);
  89.         sgt2.modify(pm[v * 2][i], deep);
  90.     }
  91. }
  92.  
  93. void cen_dec(int v) {
  94.     calc_sz(v);
  95.     int c = v, p = -1, need = sz[v] / 2;
  96.     bool run = true;
  97.     while (run) {
  98.         run = false;
  99.         for (auto to : g[c]) {
  100.             if (to == p || used[to]) continue;
  101.             if (sz[to] > need) {
  102.                 p = c;
  103.                 c = to;
  104.                 run = true;
  105.                 break;
  106.             }
  107.         }
  108.     }
  109.     used[c] = true;
  110.     segtree sgt1(kol[k - 1]), sgt2(kol[k - 1]);
  111.     for (int i = 0; i < k; i++) {
  112.         sgt1.modify(pm[c * 2 + 1][i], 0);
  113.         sgt2.modify(pm[c * 2][i], 0);
  114.     }
  115.     for (auto to : g[c]) {
  116.         if (!used[to]) {
  117.             dfs(to, c, 1, sgt1, sgt2);
  118.         }
  119.     }
  120.     for (auto to : g[c]) {
  121.         if (!used[to]) {
  122.             cen_dec(to);
  123.         }
  124.     }
  125. }
  126.  
  127. int main() {
  128. #ifdef LOCAL
  129.     freopen("input.txt", "r", stdin);
  130.     freopen("output.txt", "w", stdout);
  131. #else
  132. //    freopen("input.txt", "r", stdin);
  133. //    freopen("output.txt", "w", stdout);
  134. #endif
  135.     ios_base::sync_with_stdio(0);
  136.     cin.tie(0);
  137.     cout.tie(0);
  138.     cin >> n >> k;
  139.     pm.resize(n * 2);
  140.     set <int> st[k];
  141.     for (int i = 0; i < n; i++) {
  142.         pm[i * 2].resize(k);
  143.         pm[i * 2 + 1].resize(k);
  144.         for (int j = 0; j < k; j++) {
  145.             cin >> pm[i * 2][j];
  146.             st[j].insert(pm[i * 2][j]);
  147.         }
  148.         for (int j = 0; j < k; j++) {
  149.             cin >> pm[i * 2 + 1][j];
  150.             st[j].insert(pm[i * 2 + 1][j]);
  151.         }
  152.     }
  153.     unordered_map <int, int> nw1[k];
  154.     for (int i = 0; i < k; i++) {
  155.         int cur = 0;
  156.         for (auto it : st[i]) {
  157.             cur ++;
  158.             nw1[i][it] = cur;
  159.         }
  160.         kol[i] = cur + 1;
  161.         if (i) kol[i] = max(kol[i - 1], kol[i]);
  162.     }
  163.     for (int i = 0; i < n * 2; i++) {
  164.         for (int j = 0; j < k; j++) {
  165.             pm[i][j] = nw1[j][pm[i][j]];
  166.         }
  167.     }
  168.     for (int i = 0; i < n - 1; i++) {
  169.         int x, y;
  170.         cin >> x >> y;
  171.         x --;
  172.         y --;
  173.         g[x].pb(y);
  174.         g[y].pb(x);
  175.     }
  176.     cen_dec(0);
  177.     if (ans == INF) ans = -1;
  178.     cout << ans << endl;
  179.     return 0;
  180. }
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