Submission #1026328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026328		pera	Railway (BOI17_railway)	C++17	23 / 100	1062 ms	54692 KiB

railway

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1 , LOG = 20;
int n , m , k , T = 0;
vector<int> in(N) , out(N) , d(N) , id(N) , ans;
vector<vector<int>> g(N) , w(N) , ins(N) , ers(N) , up(N , vector<int>(LOG));
void dfs(int u , int p = 1){
   in[u] = ++T;
   d[u] = d[p] + 1;
   up[u][0] = p;
   for(int x = 0;x < (int)g[u].size();x ++){
      if(g[u][x] != p){
         dfs(g[u][x] , u);
         id[g[u][x]] = w[u][x];
      }
   }
   out[u] = T;
}
int lca(int u , int v){
   if(d[u] < d[v]){
      swap(u , v);
   }
   int s = d[u] - d[v];
   for(int bit = 0;bit < LOG;bit ++){
      if(s >> bit & 1){
         u = up[u][bit];
      }
   }
   if(u == v){
      return u;
   }
   for(int bit = LOG - 1;bit >= 0;bit --){
      if(up[u][bit] != up[v][bit]){
         u = up[u][bit];
         v = up[v][bit];
      }
   }
   return up[u][0];
}
multiset<int> DFS(int u , int p = 0){
   multiset<int> S;
   for(int x : ins[u]){
      S.insert(x);
   }
   for(int x = 0;x < (int)g[u].size();x ++){
      if(g[u][x] != p){
         auto t = DFS(g[u][x] , u);
         if((int)S.size() < (int)t.size()){
            swap(S , t);
         }
         for(int x : t){
            S.insert(x);
         }
      }
   }
   for(int x : ers[u]){
      S.erase(x);
   }
   set<int> o;
   for(int x : S){
      o.insert(x);
   }
   if((int)o.size() >= k && id[u] > 0){
      ans.push_back(id[u]);
   }
   return S;
}
int main(){
   cin >> n >> m >> k;
   for(int i = 1;i < n;i ++){
      int u , v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
      w[u].push_back(i);
      w[v].push_back(i);
   }
   dfs(1);
   for(int bit = 1;bit < LOG;bit ++){
      for(int u = 1;u <= n;u ++){
         up[u][bit] = up[up[u][bit - 1]][bit - 1];
      }
   }
   for(int i = 1;i <= m;i ++){
      int s;
      cin >> s;
      vector<int> v(s + 1);
      int min_in = n + 1 , max_out = 0;
      for(int x = 1;x <= s;x ++){
         cin >> v[x];
         min_in = min(min_in , in[v[x]]);
         max_out = max(max_out , out[v[x]]);
      }
      for(int x = 1;x <= s;x ++){
         int max_lca = v[x];
         for(int bit = LOG - 1;bit >= 0;bit --){
            if(in[up[max_lca][bit]] > min_in || out[up[max_lca][bit]] < max_out){
               max_lca = up[max_lca][bit];
            }
         }
         if(in[max_lca] > min_in || out[max_lca] < max_out){
            max_lca = up[max_lca][0];
         }
         ins[v[x]].push_back(i);
         ers[max_lca].push_back(i);
      }
   }
   DFS(1);
   cout << (int)ans.size() << endl;
   sort(ans.begin() , ans.end());
   for(int i = 0;i < (int)ans.size();i ++){
      cout << ans[i] << " ";
   }
   cout << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25