Submission #851027

#	Time	Username	Problem	Language	Result	Execution time	Memory
851027		anhphant	Railway (BOI17_railway)	C++14	100 / 100	171 ms	47700 KiB

railway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> II;
const int N = 1e5 + 3;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;

int n, m, k, f[N][20], depth[N];
vector<int> g[N], ans, anc[N];
set<int> S[N];
II ed[N];

void dfs(int u, int p){
       depth[u] = depth[p] + 1;
       f[u][0] = p;
       for(int i = 1; i < 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
       for(int id : g[u]){
              int v = ed[id].first + ed[id].second - u;
              if(v == p) continue;
              dfs(v, u);
       }
}

int lca(int u, int v){
       if(depth[u] < depth[v]) swap(u, v);
       for(int i = 19; i >= 0; i --){
              if(depth[f[u][i]] >= depth[v]) u = f[u][i];
       }
       if(u == v) return u;
       for(int i = 19; i >= 0; i --){
              if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
       }
       return f[u][0];
}

void process(int u, int id){
       for(int i : g[u]){
              if(i == id) continue;
              int v = ed[i].first + ed[i].second - u;
              process(v , i);
              if(S[v].size() > S[u].size()) swap(S[u], S[v]);
              for(auto x : S[v]) S[u].insert(x);
       }
       for(auto x : anc[u]) S[u].erase(x);
       if(S[u].size() >= k) ans.push_back(id);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i < n; i ++){
              int u, v;
              cin >> u >> v;
              g[u].push_back(i);
              g[v].push_back(i);
              ed[i] = II(u, v);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i ++){
              int s, LCA = 0;
              cin >> s >> LCA;
              S[LCA].insert(i);
              for(int j = 2; j <= s; j ++){
                     int k;
                     cin >> k;
                     LCA = lca(LCA, k);
                     S[k].insert(i);
              }
              anc[LCA].push_back(i);
    }
    process(1, 0);
    cout << ans.size() << endl;
    sort(ans.begin(), ans.end());
    for(auto x : ans) cout << x << " ";
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void process(int, int)':
railway.cpp:46:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |        if(S[u].size() >= k) ans.push_back(id);
      |           ~~~~~~~~~~~~^~~~

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