oj.uz

Submission #877260

# Submission time Handle Problem Language Result Execution time Memory
877260 2023-11-23T05:03:49 Z huutuan Pastiri (COI20_pastiri) C++14
31 / 100
 1000 ms 227624 KB 
#include<bits/stdc++.h>
#define taskname "sheep"

using namespace std;

const int inf=1e9;

struct Node{
   int val, lazy;
   Node (int a=inf, int b=0): val(a), lazy(b){}
   friend Node operator+(const Node &a, const Node &b){
      return Node(min(a.val, b.val));
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void build(int k, int l, int r, int *a){
      if (l==r){
         t[k]=Node(a[l]);
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   void apply(int k, int val){
      t[k].val+=val;
      t[k].lazy+=val;
   }
   void push(int k){
      apply(k<<1, t[k].lazy);
      apply(k<<1|1, t[k].lazy);
      t[k].lazy=0;
   }
   void point_update(int k, int l, int r, int pos, int val){
      if (l==r){
         t[k]=Node(val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      if (pos<=mid) point_update(k<<1, l, mid, pos, val);
      else point_update(k<<1|1, mid+1, r, pos, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   void update(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   int walk(int k, int l, int r, int val){
      if (l==r) return l;
      push(k);
      int mid=(l+r)>>1;
      if (t[k<<1].val==val) return walk(k<<1, l, mid, val);
      return walk(k<<1|1, mid+1, r, val);
   }
} st;

const int N=5e5+1;
int n, k, a[N], dist[N], best[N], tin[N], tout[N], tdfs, f[N], vis[N], tour[N];
vector<int> g[N], trace[N], gg[N];

void pre_dfs(int u, int p){
   tin[u]=++tdfs;
   tour[tdfs]=u;
   for (int v:g[u]) if (v!=p){
      dist[v]=dist[u]+1;
      pre_dfs(v, u);
   }
   tout[u]=tdfs;
}

void dfs(int u, int p){
   best[u]=st.t[1].val;
   vector<int> idx;
   while (st.t[1].val==best[u]){
      idx.push_back(st.walk(1, 1, n, best[u]));
      st.point_update(1, 1, n, idx.back(), inf);
      trace[u].push_back(tour[idx.back()]);
   }
   for (int i:idx) st.point_update(1, 1, n, i, best[u]);
   for (int v:g[u]) if (v!=p){
      st.update(1, 1, n, 1, n, 1);
      st.update(1, 1, n, tin[v], tout[v], -2);
      dfs(v, u);
      st.update(1, 1, n, tin[v], tout[v], 2);
      st.update(1, 1, n, 1, n, -1);
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   // freopen(taskname".inp", "r", stdin);
   // freopen(taskname".out", "w", stdout);
   cin >> n >> k;
   bool sub1=1;
   for (int i=1; i<n; ++i){
      int u, v; cin >> u >> v;
      sub1&=abs(u-v)==1;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i=1; i<=k; ++i){
      int x; cin >> x;
      a[x]=1;
   }
   // if (sub1){
   //    vector<int> v;
   //    for (int i=1; i<=n; ++i) if (a[i]) v.push_back(i);
   //    vector<int> ans;
   //    for (int i=0; i<k; ++i){
   //       if (i+1<k && (v[i+1]-v[i])%2==0){
   //          ans.push_back((v[i+1]+v[i])/2);
   //          ++i;
   //       }else ans.push_back(v[i]);
   //    }
   //    cout << ans.size() << '\n';
   //    for (int i:ans) cout << i << ' ';
   //    return 0;
   // }
   pre_dfs(1, 0);
   st.init(n);
   for (int i=1; i<=n; ++i){
      if (a[i]) st.point_update(1, 1, n, tin[i], dist[i]);
   }
   for (int i=1; i<=n; ++i){
      if (a[i]) st.point_update(1, 1, n, tin[i], dist[i]);
   }
   dfs(1, 0);
   for (int i=1; i<=n; ++i){
      sort(trace[i].begin(), trace[i].end(), [&](int x, int y){
         return dist[x]<dist[y];
      });
      for (int j:trace[i]) gg[j].push_back(i);
   }
   set<pair<pair<int, int>, int>> st;
   for (int i=1; i<=n; ++i) if (trace[i].size()) st.insert({{dist[trace[i].back()], -dist[i]}, i});
   vector<int> real;
   while (st.size()){
      int idx=st.rbegin()->second; st.erase(prev(st.end()));
      real.push_back(idx);
      for (int j:trace[idx]) if (!vis[j]){
         vis[j]=1;
         for (int l:gg[j]) if (trace[l].size() && l!=idx){
            st.erase({{dist[trace[l].back()], -dist[l]}, l});
            while (trace[l].size() && vis[trace[l].back()]) trace[l].pop_back();
            if (trace[l].size()) st.insert({{dist[trace[l].back()], -dist[l]}, l});
         }
      }
      trace[idx].clear();
   }
   cout << real.size() << '\n';
   for (int i:real) cout << i << ' ';
   return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 221896 KB Output is correct
2 Correct 610 ms 224848 KB Output is correct
3 Correct 582 ms 227624 KB Output is correct
4 Correct 751 ms 224084 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 44632 KB Output is correct
2 Correct 15 ms 44632 KB Output is correct
3 Execution timed out 1077 ms 133396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43864 KB Output is correct
2 Correct 12 ms 44084 KB Output is correct
3 Correct 12 ms 43972 KB Output is correct
4 Correct 12 ms 43868 KB Output is correct
5 Correct 12 ms 44124 KB Output is correct
6 Correct 12 ms 44124 KB Output is correct
7 Correct 11 ms 44004 KB Output is correct
8 Correct 11 ms 44124 KB Output is correct
9 Correct 12 ms 44012 KB Output is correct
10 Correct 12 ms 43924 KB Output is correct
11 Correct 23 ms 44268 KB Output is correct
12 Correct 12 ms 43964 KB Output is correct
13 Correct 74 ms 45648 KB Output is correct
14 Correct 12 ms 44124 KB Output is correct
15 Correct 12 ms 44120 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 118572 KB Time limit exceeded
2 Halted 0 ms 0 KB -