oj.uz

Submission #884148

# Submission time Handle Problem Language Result Execution time Memory
884148 2023-12-06T16:11:24 Z mgl_diamond Pastiri (COI20_pastiri) C++17
100 / 100
 482 ms 112032 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 5e5+5;

int n, k;
vector<int> adj[N];
bool sheep[N];

void solve1() {
  vector<int> rem;
  foru(i, 1, n) if (sheep[i]) rem.push_back(i);
  sort(all(rem));
  vector<int> ans;
  while (!rem.empty()) {
    int u = rem.back();
    if (rem.size() >= 2 && (rem[sz(rem)-2]+u)%2==0) {
      int v = rem[sz(rem)-2];
      ans.push_back((u+v)/2);
      rem.pop_back();
    } else ans.push_back(u);
    rem.pop_back();
  }
  cout << sz(ans) << "\n";
  fore(x, ans) cout << x << " ";
}

int kth[N], DP[1<<15], F[1<<15];
ii T[1<<15];

void solve2() {
  memset(DP, 0x3f, sizeof(DP));
  queue<int> qu;
  vector<int> tmp;
  vector<vector<int>> dist;
  int id=0;
  foru(i, 1, n) if (sheep[i]) {
    tmp.push_back(i);
    queue<int> qu;
    qu.push(i);
    dist.push_back(vector<int>(n+1, -1));
    dist[id][i] = 0;
    while (!qu.empty()) {
      int u = qu.front();
      qu.pop();
      fore(v, adj[u]) if (dist[id][v] == -1) {
        dist[id][v] = dist[id][u]+1;
        qu.push(v);
      }
    }
    kth[i] = id++;
  }
  foru(i, 1, n) {
    int mask = 0;
    int mn = N;
    fore(v, tmp)
      if (dist[kth[v]][i] < mn) {
        mn = dist[kth[v]][i];
        mask = 1<<kth[v];
      }
      else if (dist[kth[v]][i] == mn)
        mask += 1<<kth[v];
    F[mask] = i;
  }

  int full = (1<<id)-1;
  DP[0] = 0;
  foru(m, 0, full) {
    for(int sub=m; sub>0; sub=(sub-1)&m) if (F[sub] > 0) {
      if (minimize(DP[m], DP[m^sub] + 1)) {
        T[m].fi = sub;
        T[m].se = m^sub;
      }
    }
    for(int sub=m; sub>0; sub=(sub-1)&m)
      if (minimize(DP[sub], DP[m])) {
        T[sub].fi = -1;
        T[sub].se = m;
      }
  }
  cout << DP[full] << "\n";
  vector<int> shepherd;
  while(full > 0) {
    if (T[full].fi != -1) shepherd.push_back(F[T[full].fi]);
    full = T[full].se;
  }
  fore(x, shepherd) {
    cout << x << " ";
  }
}

int vis[N], dist[N], high[N], up[N];

int mark[N*2];
vector<int> block[N];

// dist[v] + high[v] == high[u]

void dfs_first(int u, int p) {
  if (!mark[dist[u]+high[u]]) mark[dist[u]+high[u]] = u;
  if (sheep[u]) {
    assert(mark[high[u]] > 0);
    up[u] = mark[high[u]];
    block[high[u]].push_back(u);
  }
  fore(v, adj[u]) {
    if (v == p) continue;
    high[v] = high[u]+1;
    dfs_first(v, u);
  }
  if (mark[dist[u]+high[u]] == u) mark[dist[u]+high[u]] = 0;
}

void dfs_second(int u) {
  vis[u] = 1;
  fore(v, adj[u]) {
    if (vis[v]) continue;
    if (dist[u]==dist[v]+1) dfs_second(v);
  }
}

void solve3() {
  queue<int> qu;
  memset(dist, -1, sizeof(dist));
  foru(i, 1, n) if (sheep[i]) { dist[i] = 0; qu.push(i); }
  while (!qu.empty()) {
    int u = qu.front();
    qu.pop();
    fore(v, adj[u]) if (dist[v] == -1) { dist[v] = dist[u]+1; qu.push(v); }
  }
  dfs_first(1, 0);
  vector<int> ans;
  ford(i, n, 0) if (!block[i].empty()) {
    fore(u, block[i]) if (!vis[u]) {
      ans.push_back(up[u]);
      dfs_second(up[u]);
    }
  }
  cout << sz(ans) << "\n";
  fore(x, ans) cout << x << " ";
}

int main() {
  setIO();

  bool line = 1;

  cin >> n >> k;
  foru(i, 2, n) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  foru(i, 1, k) {
    int node;
    cin >> node;
    sheep[node] = 1;
  }

  foru(i, 1, n)
    line &= (sz(adj[i]) <= 2);
  line &= sz(adj[1]) == 1;
  line &= sz(adj[n]) == 1;

  solve3();
//  if (line) solve1();
//  else if (k <= 15) solve2();
//  else solve3();
}

Compilation message

pastiri.cpp: In function 'void setIO()':
pastiri.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 97072 KB Output is correct
2 Correct 155 ms 97876 KB Output is correct
3 Correct 165 ms 97800 KB Output is correct
4 Correct 192 ms 112032 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 33112 KB Output is correct
2 Correct 8 ms 32856 KB Output is correct
3 Correct 288 ms 56648 KB Output is correct
4 Correct 297 ms 59228 KB Output is correct
5 Correct 352 ms 56916 KB Output is correct
6 Correct 482 ms 60380 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32600 KB Output is correct
2 Correct 8 ms 32856 KB Output is correct
3 Correct 7 ms 32860 KB Output is correct
4 Correct 7 ms 32604 KB Output is correct
5 Correct 7 ms 32860 KB Output is correct
6 Correct 8 ms 33112 KB Output is correct
7 Correct 7 ms 32604 KB Output is correct
8 Correct 9 ms 32852 KB Output is correct
9 Correct 7 ms 32856 KB Output is correct
10 Correct 9 ms 32604 KB Output is correct
11 Correct 7 ms 32604 KB Output is correct
12 Correct 7 ms 32604 KB Output is correct
13 Correct 8 ms 32604 KB Output is correct
14 Correct 7 ms 32808 KB Output is correct
15 Correct 8 ms 32860 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 59220 KB Output is correct
2 Correct 327 ms 58712 KB Output is correct
3 Correct 368 ms 61440 KB Output is correct
4 Correct 361 ms 57812 KB Output is correct
5 Correct 261 ms 57044 KB Output is correct
6 Correct 362 ms 68876 KB Output is correct
7 Correct 393 ms 65208 KB Output is correct
8 Correct 415 ms 64656 KB Output is correct
9 Correct 479 ms 59108 KB Output is correct
10 Correct 378 ms 56912 KB Output is correct
11 Correct 241 ms 61012 KB Output is correct
12 Correct 233 ms 62888 KB Output is correct
13 Correct 277 ms 65212 KB Output is correct
14 Correct 204 ms 61296 KB Output is correct
15 Correct 35 ms 36768 KB Output is correct
16 Correct 388 ms 55964 KB Output is correct
17 Correct 238 ms 57464 KB Output is correct
18 Correct 327 ms 54616 KB Output is correct
19 Correct 385 ms 65428 KB Output is correct
20 Correct 386 ms 70092 KB Output is correct
21 Correct 308 ms 57940 KB Output is correct
22 Correct 319 ms 59748 KB Output is correct