제출 #168210

#제출 시각아이디문제언어결과실행 시간메모리
168210Leonardo_PaesRailway (BOI17_railway)C++17
100 / 100
869 ms28744 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int n, m, k; int pai[maxn], nivel[maxn], siz[maxn], in[maxn], t; int chain[maxn], head[maxn], pos[maxn], c, qtd; int tree[4*maxn], lazy[4*maxn]; map<pair<int,int>,int> edges; vector<int> grafo[maxn]; void dfs(const int &u, const int &p){ siz[u] = 1, in[u] = ++t; for(int i=0; i<grafo[u].size(); i++){ int v = grafo[u][i]; if(v==p) continue; pai[v] = u, nivel[v] = nivel[u] + 1; dfs(v, u); siz[v] += siz[u]; } } void flush(const int &node, const int &l, const int &r){ tree[node] += lazy[node] * (r-l+1); if(l!=r){ lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node]; } lazy[node] = 0; } void update_tree(const int &node, const int &tl, const int &tr, const int &l, const int &r, const int &val){ flush(node, tl, tr); if(tl > r or tr < l) return; if(tl >= l and tr <= r){ lazy[node] += val; flush(node, tl, tr); return; } int mid = (tl + tr) >> 1; update_tree(2*node, tl, mid, l, r, val), update_tree(2*node+1, mid+1, tr, l, r, val); tree[node] = tree[2*node] + tree[2*node+1]; } int query_tree(const int &node, const int &tl, const int &tr, const int &l, const int &r){ flush(node, tl, tr); if(tl > r or tr < l) return 0; if(tl >= l and tr <= r) return tree[node]; int mid = (tl + tr) >> 1; return query_tree(2*node, tl, mid, l, r) + query_tree(2*node+1, mid+1, tr, l, r); } void hld(const int &u){ if(!head[c]) head[c] = u; chain[u] = c, pos[u] = ++qtd; int maior = -1, id = -1; for(int i=0; i<grafo[u].size(); i++){ int v = grafo[u][i]; if(v!=pai[u] and siz[v] > maior){ maior = siz[v], id = v; } } if(id!=-1) hld(id); for(int i=0; i<grafo[u].size(); i++){ int v = grafo[u][i]; if(v!=pai[u] and v!=id){ c++; hld(v); } } } int lca(int u, int v){ while(chain[u] != chain[v]){ if(nivel[head[chain[u]]] > nivel[head[chain[v]]]) u = pai[head[chain[u]]]; else v = pai[head[chain[v]]]; } return (nivel[u] < nivel[v] ? u : v); } void update(int u, int v){ int l = lca(u, v); while(chain[u] != chain[l]){ update_tree(1, 1, n, pos[head[chain[u]]], pos[u], 1); u = pai[head[chain[u]]]; } if(u!=l) update_tree(1, 1, n, pos[l]+1, pos[u], 1); } int query(const int &u){ //cout << query_tree(1, 1, n, pos[u], pos[u]) << endl; return (query_tree(1, 1, n, pos[u], pos[u]) >= k); } bool compara(const int &u, const int &v){ return in[u] < in[v]; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin >> n >> m >> k; int tempo = 0; for(int i=1; i<n; i++){ int u, v; cin >> u >> v; grafo[u].push_back(v); grafo[v].push_back(u); edges[{u, v}] = ++tempo; edges[{v, u}] = tempo; } dfs(1, 0); hld(1); int last, u; for(int i=1; i<=m; i++){ int s; cin >> s; vector<int> atuais; for(int j=1; j<=s; j++){ cin >> u; atuais.push_back(u); if(j==2) last = lca(atuais[j-1], atuais[j-2]); else if(j>=3) last = lca(last, atuais[j-1]); } sort(atuais.begin(), atuais.end(), compara); for(int j=0; j<atuais.size(); j++){ update(atuais[j], last); last = atuais[j]; } } vector<int> ans; for(int i=2; i<=n; i++){ if(query(i)){ ans.push_back(edges[{i, pai[i]}]); } } sort(ans.begin(), ans.end()); cout << ans.size() << "\n"; for(int i=0; i<ans.size(); i++){ cout << ans[i] << " "; } cout << "\n"; return 0; }

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

railway.cpp: In function 'void dfs(const int&, const int&)':
railway.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grafo[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
railway.cpp: In function 'void hld(const int&)':
railway.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grafo[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
railway.cpp:91:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<grafo[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:172:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<atuais.size(); j++){
                      ~^~~~~~~~~~~~~~
railway.cpp:190:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ans.size(); i++){
                  ~^~~~~~~~~~~
railway.cpp:152:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int last, u;
         ^~~~
#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...