제출 #647822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647822		mychecksedad	Railway (BOI17_railway)	C++17	30 / 100	439 ms	54752 KiB

railway

/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;




int n, m, k, dep[N], co[N], up[N][K], timer = 0, in[N], out[N], cur = 0;
vector<pair<int, int>> g[N];
bitset<10005> marked, markede;
vector<pair<int, int>> path;
vector<int> pathe, query(N), qq(N);
bool comp(int &a, int &b){
    return dep[a] < dep[b];
}
void dfs(int v, int p){
    for(auto u: g[v]){
        if(u.first != p){
            if(marked[u.first]){
                // cout << v << ' ' << u.first << '\n';
                int s = path.size() - 1;
                while(s >= 0 && !markede[path[s].second]){
                    co[path[s].second]++;
                    marked[path[s].first] = 1;
                    markede[path[s].second] = 1;
                    // cout << path[s].second << "g\n";
                    s--;
                }
            }
            path.pb(u);
            if(!markede[u.second])
                dfs(u.first, v);
            if(marked[u.first] && !markede[u.second]){
                markede[u.second] = 1, co[u.second]++; 
                // cout << u.first << ' ' << u.second << "f\n";
            }
            path.pop_back();
        }
    }
}
void pre(int v, int p){
    dep[v] = dep[p] + 1;
    in[v] = timer++;
    up[v][0] = p;
    for(auto u: g[v]){
        if(u.first != p){
            pathe.pb(u.second);
            pre(u.first, v);
        }
    }
    out[v] = timer++;
}
bool is_ancestor(int u, int v){
    return in[u] <= in[v] && out[v] <= out[u]; 
}
int lca(int u, int v){
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j = K - 1; j >= 0; --j){
        if(!is_ancestor(up[u][j], v)) u = up[u][j];
    }
    return up[u][0];
}
void dfs2(int v, int p){
    for(auto u: g[v]){
        if(u.first != p){
            dfs2(u.first, v);
            co[u.second] = cur;
        }
    }
    cur += query[v];
    cur -= qq[v];
}
void solve(){
    cin >> n >> m >> k;
    for(int i = 0; i < n - 1; ++i){
        int u, v; cin >> u >> v;
        g[u].pb({v, i});
        g[v].pb({u, i});
        co[i] = 0;
    }
    bool ok = 1;
    for(int i = 1; i <= n; ++i) if(g[i].size() > 2) ok = 0;
    if(ok){
        for(int i = 1; i <= n; ++i){
            if(g[i].size() == 1){
                dep[i] = 0;
                pre(i, i);
                break;
            }
        }
        vector<pair<int, int>> a;
        for(int i = 0; i < m; ++i){
            int c; cin >> c;
            int l = -1, r = -1;
            for(int j = 0; j < c; ++j){
                int x; cin >> x;
                if(l==-1||dep[x]<dep[l]) l=x;
                if(r==-1||dep[x]>dep[r]) r=x;
            }
            if(l != r)
                a.pb({dep[l], dep[r] - 1});
        }
        sort(all(a));
        multiset<int> se;
        int p = 0;
        for(int i = 1; i < n; ++i){
            while(p < a.size() && a[p].first == i) se.insert(a[p].second), p++;
            
            co[pathe[i - 1]] = se.size();

            se.erase(i);
        }

        vector<int> ans;
        for(int i = 0; i < n - 1; ++i) if(co[i] >= k) ans.pb(i + 1);
        cout << ans.size() << '\n';
        for(int p: ans) cout << p << ' ';
        return; 
    }
    if(k == m && n > 10000){
        dep[1] = 0;
        pre(1, 1);
        for(int j = 1; j < K; ++j)
            for(int i = 1; i <= n; ++i)
                up[i][j] = up[up[i][j - 1]][j - 1];
        for(int i = 0; i < m; ++i){
            int c, l, r; cin >> c;
            cin >> l >> r;
            int lc = lca(l, r);
            qq[lc]+=2;
            query[l]++, query[r]++;
        }
        dfs2(1, 0);
        vector<int> ans;
        for(int i = 0; i < n - 1; ++i) if(co[i] >= k) ans.pb(i + 1);
        cout << ans.size() << '\n';
        for(int p: ans) cout << p << ' ';    
        return;
    }
    dep[1] = 0;
    pre(1, 1);
    for(int i = 0; i < m; ++i){
        marked = markede = 0;
        int c; cin >> c;
        vector<int> v;
        for(int j = 0; j < c; ++j){
            int x; cin >> x;
            v.pb(x);
            marked[x] = 1;
        }
        for(int p: v) {path.pb({p, n}); dfs(p, p); path.pop_back();}
        // cout << '\n';
    }
    vector<int> ans;
    for(int i = 0; i < n - 1; ++i) if(co[i] >= k) ans.pb(i + 1);
    cout << ans.size() << '\n';
    for(int p: ans) cout << p << ' ';
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void solve()':
railway.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             while(p < a.size() && a[p].first == i) se.insert(a[p].second), p++;
      |                   ~~^~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:180:16: warning: unused variable 'aa' [-Wunused-variable]
  180 |     int T = 1, aa;
      |                ^~

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