Submission #1043335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043335		khanhtb	Railway (BOI17_railway)	C++14	100 / 100	77 ms	27340 KiB

railway

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7; 
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 1e5+8;
int n,m,k;
vector<pair<int,int>> g[N];
int h[N],up[N][20],tin[N],tdfs;
void dfs_pre(int u, int p){
    tin[u] = ++tdfs;
    for(pair<int,int> ed:g[u]){
        int v = ed.fi;
        if(v == p) continue;
        h[v] = h[u]+1;
        up[v][0] = u;
        for(int i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1];
        dfs_pre(v,u);
    }
}
int lca(int u, int v){
    if(h[u] < h[v]) swap(u,v);
    int k = h[u]-h[v];
    for(int i = 19; i >= 0; i--){
        if(k>>i&1) u = up[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
int f[N];
vector<int> ans;
void dfs(int u, int p, int id){
    for(pair<int,int> ed:g[u]){
        int v = ed.fi, i = ed.se;
        if(v == p) continue;
        dfs(v,u,i);
        f[u] += f[v];
    }
    if(f[u] >= 2*k) ans.pb(id);
}
void update(int u, int v){
    f[u]++;
    f[v]++;
    f[lca(u,v)]-=2;
}
void solve(){
    cin >> n >> m >> k;
    for(int i = 1; i < n; i++){
        int u,v;cin >> u >> v;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    dfs_pre(1,1);
    while(m--){
        int k;cin >> k;
        vector<int> s;
        for(int i = 1; i <= k; i++){
            int u;cin >> u;
            s.pb(u);
        }
        sort(all(s),[&](int a, int b){
            return tin[a] < tin[b];
        });
        for(int i = 1; i < s.size(); i++){
            update(s[i-1],s[i]);
        }
        update(s.back(),s.front());
    }
    dfs(1,1,-1);
    sort(all(ans));
    cout << ans.size() << '\n';
    for(int i:ans) cout << i << " ";
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }   
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++) {
        solve();
        cout << '\n';
    }
}

Compilation message (stderr)

railway.cpp: In function 'void solve()':
railway.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 1; i < s.size(); i++){
      |                        ~~^~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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