제출 #647807

#제출 시각아이디문제언어결과실행 시간메모리
647807mychecksedadRailway (BOI17_railway)C++17
0 / 100
69 ms60176 KiB
/* 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];
vector<pair<int, int>> g[N];
bitset<10005> marked, markede;
vector<pair<int, int>> path;
vector<int> pathe;
bool comp(int &a, int &b){
    return dep[a] < dep[b];
}
void pre(int v, int p){
    dep[v] = dep[p] + 1;
    for(auto u: g[v]) if(u.first != p) pre(u.first, v);
}
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 pre1(int v, int p){
    dep[v] = dep[p] + 1;
    for(auto u: g[v]){
        if(u.first != p){
            pathe.pb(u.second);
            pre1(u.first, 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;
                pre1(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[r]>dep[r]) r=x;
            }
            if(l != r)
                a.pb({dep[l] + 1, dep[r]});
        }
        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]] = 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; 
    }
    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:92:33: warning: self-comparison always evaluates to false [-Wtautological-compare]
   92 |                 if(r==-1||dep[r]>dep[r]) r=x;
      |                           ~~~~~~^~~~~~~
railway.cpp:101: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]
  101 |             while(p < a.size() && a[p].first == i) se.insert(a[p].second), p++;
      |                   ~~^~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:140:16: warning: unused variable 'aa' [-Wunused-variable]
  140 |     int T = 1, aa;
      |                ^~
#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...