제출 #502651

#제출 시각아이디문제언어결과실행 시간메모리
502651sumit_kk10Railway (BOI17_railway)C++17
0 / 100
1091 ms162892 KiB
#include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) #define ll long long #define F first #define S second using namespace std; const int N = 1e6 + 5, MOD = 1e9 + 7; vector<ll> graph[N]; ll dp[N][(ll) log2(100005)], n, m, s, lvl[N], tin[N], tout[N], timer = 0, u[N], v[N], fenwick[N]; void dfs(int source, int par, int level){ dp[source][0] = par; lvl[source] = level; tin[source] = ++timer; for(auto k : graph[source]) if(k != par) dfs(k, source, level + 1); tout[source] = timer; } void init(){ dfs(1, -1, 0); for(int i = 1; i <= (log2(n)); ++i) for(int j = 1; j <= n; ++j) if(dp[j][i - 1] != -1) dp[j][i] = dp[dp[j][i - 1]][i - 1]; } ll LCA(int u, int v){ if(lvl[u] > lvl[v]) swap(u, v); ll d = lvl[v] - lvl[u]; while(d){ int jump = log2(d); v = dp[v][jump]; d -= pow(2, jump); } if(v == u) return v; for(int i = log2(n); i >= 0; --i){ if(dp[v][i] != -1 && dp[v][i] != dp[u][i]){ u = dp[u][i]; v = dp[v][i]; } } return dp[v][0]; } int get(int node){ int ans = 0; for(int i = node; i >= 1; i -= (i & -i)) ans += fenwick[i]; return ans; } void upd(int node, int val){ for(int i = node; i < N; i += (i & -i)) fenwick[i] += val; } void solve(){ cin >> n >> m >> s; for(int i = 1; i <= n - 1; ++i){ cin >> u[i] >> v[i]; graph[u[i]].push_back(v[i]); graph[v[i]].push_back(u[i]); } memset(dp, -1, sizeof dp); init(); while(m--){ int r; cin >> r; vector<int> a; for(int i = 0; i < r; ++i){ int x; cin >> x; a.push_back(x); } a.push_back(a[0]); for(int i = 0; i < r; ++i){ int p = LCA(a[i], a[i + 1]); upd(tin[a[i]], 1); upd(tin[a[i + 1]], 1); upd(tin[p], -2); } } vector<int> ans; for(int i = 1; i <= n - 1; ++i){ if(lvl[u[i]] > lvl[v[i]]) swap(u[i], v[i]); int x = get(tout[v[i]]) - get(tin[v[i]] - 1); if(x >= 2*s) ans.push_back(i); } cout << ans.size() << '\n'; for(auto k : ans) cout << k << ' '; } int main() { fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }

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

railway.cpp: In function 'int main()':
railway.cpp:102:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  102 |     while(t--)
      |     ^~~~~
railway.cpp:104:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  104 |  return 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...