제출 #915418

#제출 시각아이디문제언어결과실행 시간메모리
915418starchanRailway (BOI17_railway)C++17
36 / 100
107 ms71140 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define in pair<int, int> #define f first #define s second #define pb push_back #define pob pop_back #define INF (int)1e17 #define MX (int)3e5+5 #define LOGM (int)18 #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) vector<int> adj[MX]; vector<in> edges; int pa[LOGM][MX]; int tin[MX]; int tout[MX]; int focus[MX]; int timer = 0; int label[MX]; void dfs(int u, int p) { pa[0][u] = p; tin[u] = timer++; for(int v: adj[u]) { if(v==p) continue; dfs(v, u); } tout[u] = timer; return; } int lca(int u, int v) { if(tin[u] > tin[v]) swap(u, v); if((tout[u] >= tout[v])) return u; for(int i = LOGM-1; i >= 0; i--) { if(tout[pa[i][u]] < tout[v]) u = pa[i][u]; } return pa[0][u]; } void dfs2(int u, int p) { for(int v: adj[u]) { if(v==p) continue; dfs2(v, u); focus[u]+=focus[v]; } return; } signed main() { fast(); int n, q, k; cin >> n >> q >> k; int m = n-1; while(m--) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); edges.pb({u, v}); } dfs(1, 0); int curr = 0; for(auto [x, y]: edges) { if(tin[x] >= tin[y]) swap(x, y); label[y] = ++curr; } pa[0][0] = 0; tout[0] = INF; for(int i = 1; i < LOGM; i++) { for(int j = 0; j <= n; j++) pa[i][j] = pa[i-1][pa[i-1][j]]; } while(q--) { int M; cin >> M; vector<in> v; for(int QoIGn = 1; QoIGn <= M; QoIGn++) { int u; cin >> u; v.pb({tin[u], u}); } sort(v.begin(), v.end()); for(int i = 0; i < v.size(); i++) { focus[lca(v[i].s, v[(i+1)%M].s)]--; focus[v[i].s]++; } } /*cout << "printign tin[u], tout[u]" << endl; for(int u = 1; u <= n; u++) { printf("tin[%d] = %d, tout[%d] = %d", u, tin[u], u, tout[u]); cout << endl; } cout << "printing lcas NIGELTS" << endl; for(int i = 2; i <= n; i++) { for(int j = i+1; j <= n; j++) { printf("lca(%d, %d) = %d", i, j, lca(i, j)); cout << endl; } }*/ dfs2(1, 0); int cnt = 0; vector<int> DOFINQ; for(int i = 1; i <= n; i++) { if(focus[i] >= k) DOFINQ.pb(label[i]); } cout << DOFINQ.size() << "\n"; for(int ttt: DOFINQ) cout << ttt << " "; return 0; }

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

railway.cpp: In function 'int main()':
railway.cpp:107:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
railway.cpp:129:6: warning: unused variable 'cnt' [-Wunused-variable]
  129 |  int cnt = 0;
      |      ^~~
#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...