oj.uz

Submission #877253

# Submission time Handle Problem Language Result Execution time Memory
877253 2023-11-23T05:01:05 Z huutuan Pastiri (COI20_pastiri) C++14
23 / 100
 1000 ms 230672 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;
   for (int i=1; i<n; ++i){
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i=1; i<=k; ++i){
      int x; cin >> x;
      a[x]=1;
   }
   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);
      vis[idx]=1;
      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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 222056 KB Output is correct
2 Correct 674 ms 226224 KB Output is correct
3 Correct 632 ms 230672 KB Output is correct
4 Incorrect 789 ms 228368 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 46428 KB Output is correct
2 Correct 15 ms 46684 KB Output is correct
3 Execution timed out 1046 ms 131932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 45912 KB Output is correct
2 Correct 12 ms 45976 KB Output is correct
3 Correct 12 ms 46172 KB Output is correct
4 Correct 13 ms 45916 KB Output is correct
5 Correct 14 ms 46172 KB Output is correct
6 Correct 13 ms 46168 KB Output is correct
7 Correct 13 ms 45916 KB Output is correct
8 Correct 13 ms 45916 KB Output is correct
9 Correct 13 ms 46168 KB Output is correct
10 Correct 12 ms 46092 KB Output is correct
11 Correct 23 ms 46316 KB Output is correct
12 Correct 12 ms 45912 KB Output is correct
13 Correct 69 ms 47816 KB Output is correct
14 Correct 12 ms 46168 KB Output is correct
15 Correct 12 ms 46168 KB Output is correct

Subtask #4
0 / 51.0

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