Submission #138094

#TimeUsernameProblemLanguageResultExecution timeMemory
138094Mahmoud_AdelMergers (JOI19_mergers)C++14
70 / 100
2158 ms125756 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second typedef long long ll; const int N = 5e5+5; int n, m, ans, cur, s[N], dep[N], sp[N][20], sub[N], ret[N], mark[N], acc[N], cnt[N]; vector<int> adj[N], vec[N]; void pre(int u, int p) { sub[u] = 1; dep[u] = dep[p]+1; sp[u][0] = p; for(int i=1; i<20; i++) sp[u][i] = sp[sp[u][i-1]][i-1]; for(int v : adj[u]) if(v != p) pre(v, u), sub[u] += sub[v]; } int equate(int u, int v) { int c = dep[u]-dep[v]; for(int i=0; i<20; i++) if(c & (1<<i)) u = sp[u][i]; return u; } int LCA(int u, int v) { if(dep[u] < dep[v]) swap(u, v); u = equate(u, v); if(u == v) return u; for(int i=19; i>=0; i--) if(sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i]; return sp[u][0]; } void calc(int u, int p) { for(auto v : adj[u]) if(v != p) calc(v, u), ret[u] += ret[v]; if(ret[u] == sub[u]) mark[u] = 1; } void DFS(int u, int p) { for(auto v : adj[u]) if(v != p) DFS(v, u), acc[u] += acc[v]; if(mark[u] && !acc[u]) cnt[u]=1; acc[u] += mark[u]; } int main() { scanf("%d %d", &n, &m); memset(sp, -1, sizeof sp); for(int i=1, a, b; i<n; i++) scanf("%d %d", &a, &b), adj[a].push_back(b), adj[b].push_back(a); for(int i=1; i<=n; i++) scanf("%d", &s[i]), vec[s[i]].push_back(i); pre(1, 0); for(int i=1; i<=m; i++) { if(vec[i].empty()) continue; int node = vec[i][0]; for(auto u : vec[i]) node = LCA(node, u); ret[node] += vec[i].size(); } if(n == 1) return cout << 0 << endl, 0; calc(1, 0); mark[1] = 0; DFS(1, 0); if(m > 1) { memset(sp, -1, sizeof sp); memset(mark, 0, sizeof mark); memset(dep, 0, sizeof dep); memset(ret, 0, sizeof ret); memset(sub, 0, sizeof sub); memset(acc, 0, sizeof acc); int nd; if(s[1] == 1) nd = vec[2][0]; else nd = vec[1][0]; pre(nd, 0); for(int i=1; i<=m; i++) { if(vec[i].empty()) continue; int node = vec[i][0]; for(auto u : vec[i]) node = LCA(node, u); ret[node] += vec[i].size(); } calc(nd, 0); mark[nd] = 0; DFS(nd, 0); } for(int i=1; i<=n; i++) ans += cnt[i]; cout << (ans+1)/2 << endl; }

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1, a, b; i<n; i++) scanf("%d %d", &a, &b),
                               ~~~~~~~~~~~~~~~~~~~~~~~~
  adj[a].push_back(b), adj[b].push_back(a);
  ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
mergers.cpp:48:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d", &s[i]), vec[s[i]].push_back(i);
                          ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...