제출 #480702

#제출 시각아이디문제언어결과실행 시간메모리
480702hidden1Railway (BOI17_railway)C++14
0 / 100
176 ms36484 KiB
#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #define endl "\n" typedef long long ll; template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;} template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;} template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; } template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; } const ll mod = 1e9 + 7; #ifndef LOCAL #define cerr if(false) cerr #endif const ll MAX_N = 1e5 + 10, MAX_LOG = 20;; vector<pair<ll, ll> > g[MAX_N]; ll par[MAX_N][MAX_LOG]; ll d[MAX_N]; ll ind[MAX_N], cnt[MAX_N]; ll in[MAX_N], out[MAX_N], tme; vector<ll> ans; ll n, m, k; void dfs(ll x, ll p) { par[x][0] = p; for(ll i = 1; i < MAX_LOG; i ++) { par[x][i] = par[par[x][i - 1]][i - 1]; } d[x] = d[p] + 1; in[x] = out[x] = tme ++; for(auto it : g[x]) { if(it.first == p) {continue;} ind[it.first] = it.second; dfs(it.first, x); out[x] = out[it.first]; } } ll lca(ll a, ll b) { if(d[a] < d[b]) {swap(a, b);} for(ll i = MAX_LOG - 1; i >= 0; i --) { if(d[par[a][i]] >= d[b]) { a = par[a][i]; } } if(a == b) {return a;} for(ll i = MAX_LOG - 1; i >= 0; i --) { if(par[a][i] != par[b][i]) { a = par[a][i]; b = par[b][i]; } } return par[a][0]; } ll calc(ll x, ll p) { ll now = cnt[x]; for(auto it : g[x]) { if(it.first == p) {continue;} now += calc(it.first, x); } if(now >= k) { ans.push_back(ind[x]); } cout << "for " << x << " " << ind[x] << " " << now << endl; return now; } void addCnt(vector<ll> &vert) { sort(vert.begin(), vert.end(), [](const ll a, const ll b) { return in[a] < in[b]; }); for(auto it : vert) { cnt[it] ++; } vector<pair<ll, ll> > auxVert = {{vert[0], 1}}; for(ll i = 1; i < vert.size(); i ++) { auxVert.push_back({lca(vert[i - 1], vert[i]), 0}); auxVert.push_back({vert[i], 1}); } sort(auxVert.begin(), auxVert.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b) { return in[a.first] < in[b.first]; }); stack<pair<ll, ll> > st; auto executePop = [](const pair<ll, ll> x) { cnt[x.first] -= x.second - 1; }; for(auto it : auxVert) { while(!st.empty() && !(in[st.top().first] <= in[it.first] && out[it.first] <= out[st.top().first])) { auto tp = st.top(); st.pop(); executePop(tp); if(!st.empty()) { st.top().second ++; } } if(st.empty() || st.top().first != it.first) { st.push(it); } else { st.top().second += it.second; } } while(!st.empty()) { auto tp = st.top(); st.pop(); executePop(tp); if(!st.empty()) { st.top().second ++; } else { cnt[tp.first] --; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> k; for(ll i = 0; i < n - 1; i ++) { ll a, b; cin >> a >> b; g[a].push_back({b, i + 1}); g[b].push_back({a, i + 1}); } dfs(1, 0); for(ll i = 0; i < m; i ++) { ll lst; cin >> lst; vector<ll> a(lst); for(ll j = 0; j < lst; j ++) { cin >> a[j]; } addCnt(a); } calc(1, 0); sort(ans.begin(), ans.end()); cout << ans.size() << endl; for(auto it : ans) { cout << it << " "; } return 0; }

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

railway.cpp: In function 'void addCnt(std::vector<long long int>&)':
railway.cpp:79:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 1; i < vert.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~
#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...