Submission #1099699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099699		Niosakaru	Railway (BOI17_railway)	C++11	0 / 100	4 ms	6744 KiB

railway

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define mp make_pair
#define ii pair <int,int>
 
const int N = 1e5 + 5 , Lg = 20;
 
int n , m , k , P , T , Roto , in[N] , d[N] , x[N] , dp[N] , p[N][Lg] , cnt[N];
vector <ii> adj[N];
vector <int> rt , qu[N];
 
void dfs(int u){
    in[u] = ++ T;
    for (int j = 1 ; j < Lg ; j ++) p[u][j] = p[p[u][j-1]][j-1];
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
        int v = adj[u][j].first , i = adj[u][j].second;
        if (v == p[u][0] || in[v]) continue;
        p[v][0] = u , d[v] = d[u] + 1;
        dfs(v);
    }
}
 
int __lca(int u,int v){
    if (d[u] < d[v]) swap(u,v);
    for (int i = Lg - 1 ; i >= 0 ; i --) if (d[p[u][i]] >= d[v]) u = p[u][i];
    if (u == v) return u;
    for (int i = Lg - 1 ; i >= 0 ; i --) if (p[u][i] != p[v][i]) u = p[u][i] , v = p[v][i];
    return p[u][0];
}
 
bool cmp(int& a,int& b){
    return in[a] < in[b];
}
 
void calc(int u){
    for (int j = 0 ; j < (int)adj[u].size() ; j ++){
        int v = adj[u][j].first , i = adj[u][j].second;
        if (v == p[u][0]) continue;
        calc(v);
        cnt[i] = dp[v] , dp[u] += dp[v];
    }
}
 
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    freopen("SUADUONG.INP" , "r" , stdin);
    freopen("SUADUONG.OUT" , "w" , stdout);

    cin >> n >> k >> m;
    int u , v;
    for (int i = 1 ; i < n ; i ++) 
        cin >> u >> v , adj[u].push_back(mp(v,i)) , adj[v].push_back(mp(u,i));

    dfs(1);
    for (int i = 1 ; i <= m ; i ++){
        cin >> x[i];
        qu[i].resize(x[i]);
        for (int j = 0 ; j < x[i] ; j ++) cin >> qu[i][j];
        sort(qu[i].begin() , qu[i].end() , cmp);
        Roto = qu[i][0];
        for (int j = 1 ; j < x[i] ; j ++){
            P = __lca(qu[i][j-1] , qu[i][j]);
            dp[qu[i][j]] ++ , dp[P] --;
            if (d[Roto] > d[P]) dp[Roto] ++ , dp[P] -- , Roto = P;
        }
    }
 
    calc(1);
    for (int i = 1 ; i < n ; i ++) if (cnt[i] >= k) rt.push_back(i);
    cout << rt.size() << '\n';
    sort(rt.begin() , rt.end());
    for (auto u : rt) cout << u << ' ';
 
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(long long int)':
railway.cpp:19:35: warning: unused variable 'i' [-Wunused-variable]
   19 |         int v = adj[u][j].first , i = adj[u][j].second;
      |                                   ^
railway.cpp: In function 'int main()':
railway.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("SUADUONG.INP" , "r" , stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen("SUADUONG.OUT" , "w" , stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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