Submission #889301

#	Time	Username	Problem	Language	Result	Execution time	Memory
889301		peterandvoi	Pastiri (COI20_pastiri)	C++17	100 / 100	690 ms	167348 KiB

pastiri

#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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51