| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 682017 |
2023-01-15T08:57:13 Z |
vjudge1 |
Mergers (JOI19_mergers) |
C++14 |
|
258 ms |
53152 KB |
#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;
}
Compilation message
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;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
50768 KB |
Output is correct |
| 2 |
Incorrect |
97 ms |
53152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
