제출 #391500

#제출 시각아이디문제언어결과실행 시간메모리
391500benedict0724Mergers (JOI19_mergers)C++17
0 / 100
117 ms57648 KiB
#include <bits/stdc++.h> using namespace std; vector<int> adj[500002], col[500002], tree[500002]; vector<pair<int, int>> edge; int anc[500002], co[500002], d[500002], spr[500002][20]; int link[500002], lcacol[500002]; int ans = 0; int _find(int x) { if(x == link[x]) return x; return link[x] = _find(link[x]); } void _unite(int x, int y) { x = _find(x); y = _find(y); link[x] = y; } void dep(int x, int p) { for(int i : adj[x]) { if(i == p) continue; d[i] = d[x] + 1; spr[i][0] = x; dep(i, x); } } void init(int n) { for(int t=1;t<20;t++) for(int i=1;i<=n;i++) spr[i][t] = spr[spr[i][t-1]][t-1]; } int lca(int a, int b) { if(d[a] < d[b]) swap(a, b); int dif = d[a] - d[b]; for(int i=19;i>=0;i--) if((1<<i) & dif) a = spr[a][i]; if(a == b) return a; for(int i=19;i>=0;i--) { if(spr[a][i] != spr[b][i] && spr[a][i] != 0 && spr[b][i] != 0) { a = spr[a][i]; b = spr[b][i]; } } return spr[a][0]; } int dfs(int x, int p) { int ret = lcacol[co[x]]; for(int i : adj[x]) { if(i == p) continue; int tmp = dfs(i, x); if(tmp > d[x]) edge.push_back({i, x}); else _unite(i, x); ret = min(ret, tmp); } return ret; } void solve(int x, int p) { int ret = 0; for(int i : tree[x]) { if(i == p) continue; solve(i, x); ret++; } ans += ret/2; if(p == -1 && ret%2 == 1) ans++; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; for(int i=1;i<n;i++) { int s, e; cin >> s >> e; adj[s].push_back(e); adj[e].push_back(s); } for(int i=1;i<=n;i++) link[i] = i; d[1] = 1; dep(1, -1); init(n); for(int i=1;i<=n;i++) { int c; cin >> c; co[i] = c; col[c].push_back(i); } for(int i=1;i<=k;i++) { lcacol[i] = col[i][0]; for(int j = 1; j < col[i].size();j++) { lcacol[i] = lca(lcacol[i], col[i][j]); } lcacol[i] = d[lcacol[i]]; } dfs(1, -1); for(auto u : edge) { int s = u.first, e = u.second; s = _find(s); e = _find(e); tree[s].push_back(e); tree[e].push_back(s); } solve(_find(1), -1); cout << ans; }

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

mergers.cpp: In function 'int main()':
mergers.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j = 1; j < col[i].size();j++)
      |                        ~~^~~~~~~~~~~~~~~
#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...