제출 #879657

#제출 시각아이디문제언어결과실행 시간메모리
879657KarootRailway (BOI17_railway)C++17
7 / 100
144 ms48340 KiB
#include <iostream> #include <cmath> #include <map> #include <unordered_map> #include <set> #include <queue> #include <vector> #include <string> #include <algorithm> #include <iomanip> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() typedef long long ll; ll linf = 1e15+1; using namespace std; inline void scoobydoobydoo(){ ios::sync_with_stdio(false); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int MAXN = 1e5+1; set<pair<int, int> > s[MAXN]; int wutS[MAXN]; vector<int> children[MAXN]; int n, m, k; int q = 0; vector<pair<int, int>> adj[MAXN]; int nodeId[MAXN], binPar[MAXN][20]; vector<pair<int, int> > elemsNode[MAXN]; vector<pair<int, int>> ans; int depthNode[MAXN]; void rootTree(int node, int parent, int depth){ depthNode[node] = depth; //cout << node << " " << parent << " " << depth << " " << binPar[node][0] << endl; for (auto& e : adj[node]){ if (e.first != parent){ children[node].push_back(e.first); nodeId[e.first] = e.second; binPar[e.first][0] = node; rootTree(e.first, node, depth+1); } } } void smallerToLarger(int node, int depth){ if (children[node].size() == 0){ wutS[node] = q; for (auto& e : elemsNode[node]){ if (depth+1 != e.first)s[q].insert(e); } ans.push_back({s[q].size(), node}); q++; /*cout << "LO " << node << " " << wutS[node] << endl; for (auto& e : s[wutS[node]]){ cout << e.first << "," << e.second << " "; } cout << endl << endl;*/ return; } int maxiChild = -1, maxi = -1; for (auto& e : children[node]){ smallerToLarger(e, depth+1); //cout << e << ": " << node << ": " << wutS[e] << " " << (*s[wutS[e]].begin()).first << " " << (*s[wutS[e]].begin()).first << " " << s[wutS[e]].size() << endl; int sZ = s[wutS[e]].size(); if (sZ > maxi){ //cout << "should be here" << endl; maxiChild = e; maxi = s[wutS[e]].size(); } } //cout << node << " _ " << maxiChild << endl; wutS[node] = wutS[maxiChild]; for (auto& e : children[node]){ if (e != maxiChild){ for (auto& l : s[wutS[e]]){ if (l.first != depth+1) s[wutS[node]].insert(l); } } } for (auto& e : elemsNode[node]){ if (depth+1 != e.first)s[wutS[node]].insert(e); } /*cout << "Ye1 " << node << " " << wutS[node] << endl; for (auto& e : s[wutS[node]]){ cout << e.first << "," << e.second << " "; } cout << endl << endl;*/ while (true){ auto it = s[wutS[node]].lower_bound({depth, 0}); if (it == s[wutS[node]].end())break; s[wutS[node]].erase(it); } /*cout << "Ye2 " << node << " " << wutS[node] << endl; for (auto& e : s[wutS[node]]){ cout << e.first << "," << e.second << " "; } cout << endl << endl;*/ ans.push_back({s[wutS[node]].size(), node}); return; } void initBinPar(){ binPar[0][0] = 0; for (int j = 1; j < 20; j++){ for (int i = 0; i < n; i++){ binPar[i][j] = binPar[binPar[i][j-1]][j-1]; } } return; } int jump(int node, int x){ for (int i = 20; i >= 0; i--){ if (x & (1<<i))node = binPar[node][i]; } return node; } int lca(vector<int> v){ int miniD = 1e7; for (auto e : v){ miniD = min(miniD, depthNode[e]); } for (int i = 0; i < v.size(); i++){ v[i] = jump(v[i], depthNode[v[i]]-miniD); } bool isAllSame = true; for (int i = 0; i < v.size(); i++){ if (v[i] != v[0])isAllSame = false; } if (isAllSame)return miniD; for (int i = 20; i >= 0; i--){ bool works = true; int firstVal = binPar[v[0]][i]; for (int x : v){ if (binPar[x][i] != firstVal)works = false; } if (!works){ for (int j = 0; j < v.size(); j++){ v[j] = binPar[v[j]][i]; } } } return depthNode[binPar[v[0]][0]]; } int main(){ scoobydoobydoo(); cin >> n >> m >> k; for (int i = 0; i < n-1; i++){ int a, b; cin >> a >> b; a--; b--; adj[a].push_back({b, i+1}); adj[b].push_back({a, i+1}); } rootTree(0, 0, 0); initBinPar(); /*for (int i = 0; i < n; i++){ cout << "N" << i << ": " << nodeId[i] << " "; } cout << endl; */ for (int i = 0; i < m; i++){ int l; cin >> l; vector<int> v; for (int j = 0; j < l; j++){ int t; cin >> t; v.push_back(--t); } int d = lca(v); //cout << d << endl; for (int x : v){ elemsNode[x].push_back({d, i}); } } /*for (int i = 0; i < n; i++){ cout << i << ": "; for (auto& e : elemsNode[i]){ cout << e.first << ", " << e.second << " "; } cout << endl; }*/ smallerToLarger(0, 0); /*for (int i = 0; i <= q; i++){ cout << i << ": "; for (auto& e : s[i]){ cout << e.first << ", " << e.second << " "; } cout << endl; }*/ sort(rall(ans)); vector<int> nAns; for (int i = 0; i < ans.size() && ans[i].first >= k; i++){ //cout << ans[i].first << " " << ans[i].second << "; "; nAns.push_back(nodeId[ans[i].second]); } //cout << endl; sort(all(nAns)); cout << nAns.size() << endl; for (auto& e : nAns){ cout << e << " "; } cout << endl; return 0; }

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

railway.cpp: In function 'int lca(std::vector<int>)':
railway.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < v.size(); i++){
      |                     ~~^~~~~~~~~~
railway.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int i = 0; i < v.size(); i++){
      |                     ~~^~~~~~~~~~
railway.cpp:162:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             for (int j = 0; j < v.size(); j++){
      |                             ~~^~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:224:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for (int i = 0; i < ans.size() && ans[i].first >= k; 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...