제출 #682017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682017		vjudge1	Mergers (JOI19_mergers)	C++14	0 / 100	258 ms	53152 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N (ll)(5e5+5)
#define fi first
#define se second
ll n, k, sk[N], p[21][N], st[N], ft[N], t[N], ct, gp[N], d[N], ans;
vector<ll> g[N], u[N];
void dfs(ll s, ll par) {
	st[s] = ++ct; u[sk[s]].push_back(s); p[0][s] = par; for (int i = 1; i < 21; i++) p[i][s] = p[i - 1][p[i - 1][s]];
	for (auto x : g[s]) if (x != par) dfs(x, s); ft[s] = ++ct; 
}
inline ll glca(ll x, ll y) { if (x == y) return x; if (st[x] < st[y]) swap(x, y); for (int i = 20; i > -1; i--) if (!(st[p[i][x]] <= st[y] && ft[p[i][x]] >= ft[y])) x = p[i][x]; return p[0][x]; }
void dfs2(ll s, ll par) { for (auto x : g[s]) if (x != par) dfs2(x, s), t[s] += t[x]; }
void dfss(ll s, ll par) { for (auto x : g[s]) if (x != par) { if (t[x] == 0) gp[x] = ++ct, d[gp[s]]++, d[ct]++; else gp[x] = gp[s]; dfss(x, s); } }
int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll a, b; cin >> n >> k; for (int i = 1; i < n; i++) cin >> a >> b, g[a].push_back(b), g[b].push_back(a);
	for (int i = 1; i <= n; i++) cin >> sk[i]; if (n == 1) return cout << 0, 0;
	dfs(1, 1);
	for (int i = 1; i <= k; i++) for (int j = 1; j < u[i].size(); j++) ++t[u[i][j]], ++t[u[i][j - 1ll]], ----t[glca(u[i][j], u[i][j - 1ll])];
	ct = 1; gp[1] = 1; dfs2(1, 1); dfss(1, 1);if (ct == 1) return cout << 0, 0;
	for (int i = 1; i <= ct; i++) if (d[i] == 1) ans++; cout << ans - 1;
}

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

mergers.cpp: In function 'void dfs(long long int, long long int)':
mergers.cpp:11:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   11 |  for (auto x : g[s]) if (x != par) dfs(x, s); ft[s] = ++ct;
      |  ^~~
mergers.cpp:11:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   11 |  for (auto x : g[s]) if (x != par) dfs(x, s); ft[s] = ++ct;
      |                                               ^~
mergers.cpp: In function 'int main()':
mergers.cpp:19:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 |  for (int i = 1; i <= n; i++) cin >> sk[i]; if (n == 1) return cout << 0, 0;
      |  ^~~
mergers.cpp:19:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   19 |  for (int i = 1; i <= n; i++) cin >> sk[i]; if (n == 1) return cout << 0, 0;
      |                                             ^~
mergers.cpp:21:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 1; i <= k; i++) for (int j = 1; j < u[i].size(); j++) ++t[u[i][j]], ++t[u[i][j - 1ll]], ----t[glca(u[i][j], u[i][j - 1ll])];
      |                                               ~~^~~~~~~~~~~~~
mergers.cpp:23:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |  for (int i = 1; i <= ct; i++) if (d[i] == 1) ans++; cout << ans - 1;
      |  ^~~
mergers.cpp:23:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |  for (int i = 1; i <= ct; i++) if (d[i] == 1) ans++; cout << ans - 1;
      |                                                      ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30