Submission #889220

#	Time	Username	Problem	Language	Result	Execution time	Memory
889220		peterandvoi	Pastiri (COI20_pastiri)	C++17	8 / 100	1034 ms	103392 KiB

pastiri

#include <bits/stdc++.h>

using namespace std;

#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

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

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

#define N   500005

int n, k;
int x[N];
int h[N];
int sz[N];
int par[N];
int head[N];
vector<int> g[N];

void dfs(int u = 1) {
  sz[u] = 1;
  for (int v : g[u]) {
    if (v != par[u]) {
      par[v] = u;
      h[v] = h[u] + 1;
      dfs(v);
      sz[u] += sz[v];
    }
  }  
  for (int &v : g[u]) {
    if (v == par[u]) {
      swap(v, g[u].back());
      g[u].pop_back();
      break;
    }
  }
}

void hld(int u = 1, int h = 1) {
  head[u] = h;
  if (g[u].size()) {
    int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
      return sz[i] < sz[j];
    });
    hld(x, h);
    for (int v : g[u]) {
      if (v != x) {
        hld(v, v);
      }
    }
  }
}

int lca(int u, int v) {
  while (head[u] != head[v]) {
    if (sz[head[u]] > sz[head[v]]) {
      swap(u, v);
    }
    u = par[head[u]];
  }  
  return sz[u] < sz[v] ? v : u;
}

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 << " ";
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  file("SHEEP");
  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();
  hld();
  for (int i = 1; i <= k; ++i) {
    cin >> x[i];
  }
  if (sub1::valid_input()) {
    sub1::solve();
  }
  if (sub2::valid_input()) {
    sub2::solve();
  }
}

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:197:3: note: in expansion of macro 'file'
  197 |   file("SHEEP");
      |   ^~~~
pastiri.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:197:3: note: in expansion of macro 'file'
  197 |   file("SHEEP");
      |   ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51