oj.uz

Submission #889301

# Submission time Handle Problem Language Result Execution time Memory
889301 2023-12-19T10:04:22 Z peterandvoi Pastiri (COI20_pastiri) C++17
100 / 100
 690 ms 167348 KB 
#include <bits/stdc++.h>

using namespace std;

#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "

#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(x) (1LL << (x))

#define N    500005
#define LOG  20

int n, k;
int x[N];
int h[N];
int par[N];
int st[LOG][N << 1];
int tin[N];
int tout[N];
int lg[N << 1];
vector<int> g[N];

int min_by_time(int u, int v) {
  return (tin[u] < tin[v] ? u : v);
}

int order;

void dfs(int u = 1) {
  tin[u] = ++order;
  st[0][order] = u;
  for (int v : g[u]) {
    if (!tin[v]) {
      h[v] = h[u] + 1;
      par[v] = u;
      dfs(v);
      st[0][++order] = u;
    }
  }
  tout[u] = order;
}

void build_spt() {
  for (int i = 2; i <= order; ++i) {
    lg[i] = lg[i >> 1] + 1;
  }  
  for (int j = 1; j <= lg[order]; ++j) {
    for (int i = 1; i + MASK(j) - 1 <= order; ++i) {
      st[j][i] = min_by_time(st[j - 1][i], st[j - 1][i + MASK(j - 1)]);
    }
  }
}

int lca(int u, int v) {
  int L = min(tin[u], tin[v]);
  int R = max(tout[u], tout[v]);
  int k = lg[R - L + 1];
  return min_by_time(st[k][L], st[k][R - MASK(k) + 1]);  
}

int dist(int u, int v) {
  return h[u] + h[v] - 2 * h[lca(u, v)];
}

template<class A, class B>
bool mini(A &a, const B &b) {
  return a > b ? (a = b), true : false;
}

namespace sub1 {
  bool valid_input() {
    bool test = true;
    for (int i = 1; i <= n; ++i) {
      for (int j : g[i]) {
        test &= (abs(j - i) == 1);
      }
    }
    return test;
  }
  
  int dp[2][N];
  int child[2][N];
  pair<int, int> par[2][N];
  
  bool mid(int l, int r) {
    return (l > 0 && (r - l) % 2 == 0);  
  }
  
  void solve() {
    sort(x + 1, x + k + 1);
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = dp[1][0] = 0;
    for (int i = 1; i <= k; ++i) {
      // case 1: dat 1 con phu i va i - 1 (neu x[i] - x[i - 1] & 1)
      if (mid(x[i - 1], x[i])) {
        if (mini(dp[1][i], dp[0][i - 1] + 1)) {
          child[1][i] = x[i - 1] + (x[i] - x[i - 1]) / 2;
          par[1][i] = {0, i - 1};
        }
      }
      // case 2: dat tai i
      if (mini(dp[1][i], dp[1][i - 1] + 1)) {
        child[1][i] = x[i];
        par[1][i] = {1, i - 1};
      }
      // case 3: k dat tai i
      dp[0][i] = dp[1][i - 1];
      par[0][i] = {1, i - 1};
    }
    int t = 1;
    vector<int> res;
    do {
      if (child[t][k]) {
        res.emplace_back(child[t][k]);
      }
      pair<int, int> prv = par[t][k];
      t = prv.first;
      k = prv.second;
    } while (k != 0);
    cout << res.size() << "\n";
    for (int idx : res) {
      cout << idx << " ";
    }
    exit(0);
  }
}

namespace sub2 { 
  bool valid_input() {
    return k <= 15;
  }  
  
  int g[MASK(15)];
  int child[MASK(15)];
  pair<int, int> prv[MASK(15)];
  vector<int> res;
  
  void dfs(int u) {
    if (g[u] <= 1) {
      if (child[u]) {
        res.emplace_back(child[u]);
      }
      return;
    }
    dfs(prv[u].first);
    dfs(prv[u].second);
  }
  
  void solve() {
    memset(g, 0x3f, sizeof(g));
    g[0] = 0;
    for (int i = 1; i <= n; ++i) {
      int mn = n + 1, mask = 0;
      for (int j = 1; j <= k; ++j) {
        int dis = dist(i, x[j]);
        if (mn > dis) {
          mn = dis;
          mask = MASK(j - 1);
        } else if (mn == dis) {
          mask |= MASK(j - 1);
        }
      }
      if (mini(g[mask], 1)) {
        child[mask] = i;
      }
    }
    for (int mask = 0; mask < MASK(k); ++mask) {
      for (int smask = mask; smask; smask = (smask - 1) & mask) {
        if (mini(g[smask], g[mask])) {
          child[smask] = child[mask];
        }
      }
    }
    for (int mask = 0; mask < MASK(k); ++mask) {
      for (int smask = mask; smask; smask = (smask - 1) & mask) {
        if (mini(g[mask], g[smask] + g[mask ^ smask])) {
          prv[mask] = {smask, mask ^ smask};
        }
      }
    }
    dfs(MASK(k) - 1);
    cout << res.size() << "\n";
    for (int idx : res) {
      cout << idx << " ";
    }
    exit(0);
  }
}

namespace sub3 {
  bool valid_input() {
    return n <= 2000;
  }
  
  int mn[2005];
  bool vis[2005];
  
  void solve() {
    for (int i = 1; i <= n; ++i) {
      mn[i] = n + 1;
      for (int j = 1; j <= k; ++j) {
        mn[i] = min(mn[i], dist(i, x[j]));
      }
    }
    sort(x + 1, x + k + 1, [&](int x, int y) {
      return h[x] > h[y];
    });
    vector<int> res;  
    for (int i = 1; i <= k; ++i) {
      int u = x[i];
      if (!vis[u]) {
        int v = -1;
        for (int j = 1; j <= n; ++j) {
          if (mn[j] == dist(u, j)) {
            if (v == -1 || h[v] > h[j]) {
              v = j;
            }
          }
        }
        res.emplace_back(v);
        for (int j = 1; j <= k; ++j) {
          if (mn[v] == dist(x[j], v)) {
            vis[x[j]] = true;
          }
        }
      }
    }
    cout << res.size() << "\n";
    for (int idx : res) {
      cout << idx << " ";
    }
    exit(0);
  }
}

namespace sub4 {
  int mn[N];
  bool vis[N];
  
  void bfs(int src) {
    vis[src] = true;
    queue<int> q;
    q.emplace(src);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int v : g[u]) {
        if (!vis[v] && mn[v] + 1 == mn[u]) {
          vis[v] = true;
          q.emplace(v);
        }
      }
    }
  }
  
  void solve() {
    memset(mn, -1, sizeof(mn));
    queue<int> q;
    for (int i = 1; i <= k; ++i) {
      mn[x[i]] = 0;
      q.emplace(x[i]);
    }  
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (int v : g[u]) {
        if (mn[v] == -1) {
          mn[v] = mn[u] + 1;
          q.emplace(v);
        }
      }
    }
    sort(x + 1, x + k + 1, [&](int i, int j) {
      return h[i] > h[j];
    });
    vector<int> res;
    for (int i = 1; i <= k; ++i) {
      int u = x[i];
      if (!vis[u]) {
        int v = u;
        while (mn[par[v]] + h[par[v]] == h[u]) {
          v = par[v];
        } 
        res.emplace_back(v);
        bfs(v);
      }
    }
    cout << res.size() << "\n";
    for (int idx : res) {
      cout << idx << " ";
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  dfs();
  build_spt();
  for (int i = 1; i <= k; ++i) {
    cin >> x[i];
  }
  if (sub1::valid_input()) {
    sub1::solve();
  }
  if (sub2::valid_input()) {
    sub2::solve();
  }
  if (sub3::valid_input()) {
    sub3::solve();
  }
  sub4::solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 160072 KB Output is correct
2 Correct 168 ms 160084 KB Output is correct
3 Correct 182 ms 160196 KB Output is correct
4 Correct 223 ms 167348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 53852 KB Output is correct
2 Correct 20 ms 54004 KB Output is correct
3 Correct 678 ms 122804 KB Output is correct
4 Correct 689 ms 125028 KB Output is correct
5 Correct 669 ms 122732 KB Output is correct
6 Correct 690 ms 125648 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 49756 KB Output is correct
2 Correct 13 ms 49792 KB Output is correct
3 Correct 31 ms 49756 KB Output is correct
4 Correct 27 ms 50012 KB Output is correct
5 Correct 34 ms 49756 KB Output is correct
6 Correct 28 ms 49756 KB Output is correct
7 Correct 11 ms 49792 KB Output is correct
8 Correct 11 ms 49752 KB Output is correct
9 Correct 11 ms 49756 KB Output is correct
10 Correct 16 ms 49796 KB Output is correct
11 Correct 14 ms 49756 KB Output is correct
12 Correct 14 ms 47712 KB Output is correct
13 Correct 29 ms 49756 KB Output is correct
14 Correct 19 ms 49840 KB Output is correct
15 Correct 23 ms 49756 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 125868 KB Output is correct
2 Correct 491 ms 132492 KB Output is correct
3 Correct 585 ms 135080 KB Output is correct
4 Correct 513 ms 131624 KB Output is correct
5 Correct 431 ms 130560 KB Output is correct
6 Correct 516 ms 139832 KB Output is correct
7 Correct 529 ms 137812 KB Output is correct
8 Correct 579 ms 137300 KB Output is correct
9 Correct 554 ms 132012 KB Output is correct
10 Correct 432 ms 131744 KB Output is correct
11 Correct 313 ms 133784 KB Output is correct
12 Correct 336 ms 136532 KB Output is correct
13 Correct 348 ms 138540 KB Output is correct
14 Correct 264 ms 135252 KB Output is correct
15 Correct 42 ms 80468 KB Output is correct
16 Correct 482 ms 129876 KB Output is correct
17 Correct 335 ms 131068 KB Output is correct
18 Correct 397 ms 127316 KB Output is correct
19 Correct 490 ms 137296 KB Output is correct
20 Correct 463 ms 140812 KB Output is correct
21 Correct 377 ms 131856 KB Output is correct
22 Correct 461 ms 132436 KB Output is correct