oj.uz

답안 #535656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535656 2022-03-10T20:20:57 Z nemethm Railway (BOI17_railway) C++17
36 / 100
 346 ms 74320 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list>

using namespace std;
using ll = long long int;

vector<int> g[100100];
int dp[100100][30];
set<int> in[100100], out[100100];
int level[100100];
map<pair<int,int>,int> id;
vector<int> ans;
int k;
void dfs(int node, int prev = 0, int l = 1){
  level[node] = l;
  dp[node][0] = prev;
  for(auto i : g[node]){
    if(i != prev){
      dfs(i, node, l + 1);
    }
  }
}

int jump(int a, int x){
    for(int i = 0; i < 20; ++i){
        if((x >> i) & 1){
            a = dp[a][i];
        }
    }
    return a;
}

int lca(int a, int b){
    if(level[a] < level[b]) swap(a,b);
    a = jump(a, level[a] - level[b]);
    if(a == b) return a;
    for(int i = 20; i >= 0; --i){
        if(dp[a][i] != dp[b][i]){
            a = dp[a][i], b = dp[b][i];
        }
    }
    return dp[a][0];
}

set<int> solve(int node, int prev = -1){
  set<int> open = in[node];
  for(auto i : g[node]){
    if(i != prev){
      set<int> a = solve(i, node);
      if(a.size() >= k){
        ans.push_back(id[{node, i}]);
      }
      if(a.size() > open.size()) swap(a, open);
      for(auto& j : a){
        open.emplace(j);
      }
    }
  }
  for(auto& i : out[node]){
    open.erase(i);
  }
  return open;
}

int main()
{
  int n, m;
  cin >> n >> m >> k;
  for(int i = 0; i < n - 1; ++i){
    ll a, b;
    cin >> a >> b;
    g[a].emplace_back(b), g[b].emplace_back(a);
    id[{a,b}] = id[{b,a}] = i + 1;
  }
  dfs(1);
  for(int i = 1; i < 20; ++i){
    for(int node = 1; node <= n; ++node){
      dp[node][i] = dp[dp[node][i - 1]][i - 1];
    }
  }
  while(m--){
    int meret;
    cin >> meret;
    vector<int> v(meret);
    for(auto& i : v) cin >> i;
    for(int i = 1; i < meret; ++i){
      int c = lca(v[i], v[0]);
      in[v[i]].emplace(m);
      in[v[0]].emplace(m);
      out[c].emplace(m);
    }
  }
  solve(1);
  sort(begin(ans), end(ans));
  cout << ans.size() << endl;
  for(auto& i : ans){
    cout << i << " ";
  }
  cout << endl;
  return 0;
}

Compilation message

railway.cpp: In function 'std::set<int> solve(int, int)':
railway.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |       if(a.size() >= k){
      |          ~~~~~~~~~^~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 19 ms 15060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 19 ms 15060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 72148 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 289 ms 71776 KB Output is correct
4 Correct 277 ms 71352 KB Output is correct
5 Correct 271 ms 69784 KB Output is correct
6 Correct 284 ms 74320 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 60968 KB Output is correct
2 Correct 341 ms 51588 KB Output is correct
3 Correct 342 ms 52276 KB Output is correct
4 Correct 337 ms 52644 KB Output is correct
5 Correct 346 ms 52056 KB Output is correct
6 Correct 288 ms 61300 KB Output is correct
7 Correct 287 ms 61284 KB Output is correct

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 60968 KB Output is correct
2 Correct 341 ms 51588 KB Output is correct
3 Correct 342 ms 52276 KB Output is correct
4 Correct 337 ms 52644 KB Output is correct
5 Correct 346 ms 52056 KB Output is correct
6 Correct 288 ms 61300 KB Output is correct
7 Correct 287 ms 61284 KB Output is correct
8 Correct 273 ms 58752 KB Output is correct
9 Correct 273 ms 59084 KB Output is correct
10 Correct 252 ms 69512 KB Output is correct
11 Correct 247 ms 69536 KB Output is correct
12 Incorrect 224 ms 45884 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 19 ms 15060 KB Output isn't correct
3 Halted 0 ms 0 KB -