Submission #1344401

#TimeUsernameProblemLanguageResultExecution timeMemory
134440124ta_tdanhRailway (BOI17_railway)C++20
29 / 100
98 ms41040 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
#define ce cout<<endl;
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using T = pair<ll,int>;
const ll INF = 1e18;
const int N = 1e5;
const int MAXM = 4200005;
const int LOG2 = 17;
const int inv = 1112;
const int MOD =998244353 ;
int dx[]= {0,0,-1,1};
int dy[] = {1 , - 1 , 0 , 0};
// Author : T_Danh - Tri An High School 
ll mypow(ll a,  ll b , ll mod ){
    ll res = 1;
    a %= mod;
    while(b){
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int n ,m , k;
vector<pii> adj[N + 1];
int par[N + 1][LOG2 + 1];
int h[N + 1];
vector<int> sugg[N + 1];
int prefix[N  + 1] , val[N + 1];
int ed[N + 1];
void dfs(int u , int p){
    par[u][0] = p;
    for(pii to :adj[u])if(to.fi != p){
        h[to.fi] = h[u] + 1;
        ed[to.fi] = to.se;
        dfs(to.fi , u);
    }
}
int LCA(int u , int v){
    if(h[u] < h[v]) swap(u , v);
    FOR2(i,LOG2 , 0){
        if(h[u] - (1 << i) >= h[v]){
            u = par[u][i];
        }
    }
    if(u == v) return u;
    FOR2(i,LOG2 , 0){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
set<int> cal(int u , int p){
    set<int> cur;
    for(int i : sugg[u]){
        cur.insert(i);
    }
    for(pii to : adj[u]) if(to.fi != p){
        set<int> tmp = cal(to.fi , u);
        prefix[u] += prefix[to.fi];
        if(tmp.size() > cur.size()) swap(cur , tmp);
        for(int i : tmp) cur.insert(i);
    }
    val[u] = cur.size() + prefix[u];
    return cur;
}
void solve() {
    cin >> n >> m >> k;
    FOR(i,1,n-1){
        int u , v;
        cin >> u >> v;
        adj[u].eb(v , i);
        adj[v].eb(u , i);
    }
    dfs(1,1);
    FOR(j,1,LOG2){
        FOR(i,1,n){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
    FOR(i,1,m){
        int s;
        cin>>s;
        int pre = -1;
        FOR(j,1,s){
            int x;

            cin >> x;
            if(pre == -1) pre = x;
            else{
                pre = LCA(pre , x);
            }
            sugg[x].eb(i);
        }
        prefix[pre] -= s;
    }
    cal(1,1);
    vector<int> ans;
    FOR(i,2,n){
        if(val[i] >= k){
            ans.eb(i);
        }
    }
    cout << ans.size() <<endl;
    for(int i : ans){
        cout << ed[i] << " " ;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define NAME "runaway"
    if (fopen(NAME".in", "r"))
        freopen(NAME".in", "r", stdin),
        freopen(NAME".out", "w", stdout);
    solve();
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(NAME".in", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...