제출 #1367823

#제출 시각아이디문제언어결과실행 시간메모리
1367823SmuggingSpunRailway (BOI17_railway)C++20
100 / 100
50 ms22984 KiB
#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int lim = 1e5 + 5;
const int LG = 17;
int n, m, k, tdfs = 0, a[lim], b[lim], v2e[lim], low[lim], tail[lim], h[lim], f[lim], up[LG][lim];
vector<int>g[lim];
void dfs(int s){
  low[s] = ++tdfs;
  for(int& i : g[s]){
    int d = a[i] ^ b[i] ^ s;
    if(d != up[0][s]){
      h[d] = h[up[0][d] = s] + 1;
      v2e[d] = i;
      dfs(d);
    }
  }
  tail[s] = tdfs;
}
int lca(int u, int v){
  if(h[u] < h[v]){
    swap(u, v);
  }
  for(int x = h[u] - h[v], i = 0; i < LG; i++){
    if(x >> i & 1){
      u = up[i][u];
    }
  }
  if(u == v){
    return u;
  }
  for(int i = LG - 1; i > -1; i--){
    if(up[i][u] != up[i][v]){
      u = up[i][u];
      v = up[i][v];
    }
  }
  return up[0][u];
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n >> m >> k;
  for(int i = 1; i < n; i++){
    cin >> a[i] >> b[i];
    g[a[i]].push_back(i);
    g[b[i]].push_back(i);
  }
  memset(f, up[0][0] = up[0][1] = h[1] = 0, sizeof(f));
  dfs(1);
  for(int i = 1; i < LG; i++){
    for(int j = 0; j <= n; j++){
      up[i][j] = up[i - 1][up[i - 1][j]];
    }
  }
  for(int _ = 0; _ < m; _++){
    int siz;
    cin >> siz;
    vector<int>ver(siz);
    for(int& x : ver){
      cin >> x;
    }
    sort(ver.begin(), ver.end(), [&] (int i, int j){
      return low[i] < low[j];
    });
    for(int i = siz - 2; i > -1; i--){
      ver.push_back(lca(ver[i], ver[i + 1]));
    }
    sort(ver.begin(), ver.end(), [&] (int i, int j){
      return low[i] < low[j];
    });
    ver.resize(unique(ver.begin(), ver.end()) - ver.begin());
    vector<int>stk(1, ver[0]);
    for(int i = 1; i < ver.size(); stk.push_back(ver[i++])){
      while(tail[stk.back()] < low[ver[i]]){
        stk.pop_back();
      }
      f[ver[i]]++;
      f[stk.back()]--;
    }
  }
  vector<int>p(n - 1);
  iota(p.begin(), p.end(), 2);
  sort(p.begin(), p.end(), [&] (int i, int j){
    return h[i] > h[j];
  });
  for(int& x : p){
    for(int& i : g[x]){
      int y = a[i] ^ b[i] ^ x;
      if(h[y] > h[x]){
        f[x] += f[y];
      }
    }
  }
  vector<int>ans;
  for(int i = 2; i <= n; i++){
    if(f[i] >= k){
      ans.push_back(v2e[i]);
    }
  }
  sort(ans.begin(), ans.end());
  cout << ans.size() << "\n";
  for(int& x : ans){
    cout << x << " ";
  }
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'int main()':
railway.cpp:43:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…