| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 133912 |
2019-07-21T18:05:07 Z |
ekrem |
Mergers (JOI19_mergers) |
C++ |
|
252 ms |
111984 KB |
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define LOGN 20
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
int n, k, root, ans, deg[N], l[N], a[N], der[N], par[LOGN + 5][N];
vector < int > g[N], cik[N];
int amk, of, fl;
set < int > s[N];
set < int > :: iterator it;
void hazirla(int node, int pr, int dr){
der[node] = dr;
par[0][node] = pr;
for(int i = 0; i < g[node].size(); i++)
if(coc != pr)
hazirla(coc, node, dr + 1);
}
int lca(int u, int v){
if(!u or !v)
return u + v;
if(der[u] < der[v])
swap(u, v);
for(int i = LOGN; i >= 0; i--)
if(der[par[i][u]] >= der[v])
u = par[i][u];
if(u == v)
return u;
for(int i = LOGN; i >= 0; i--)
if(par[i][u] != par[i][v]){
u = par[i][u];
v = par[i][v];
}
return par[0][u];
}
int dfs(int node, int par){
int don = 0;
for(int i = 0; i < g[node].size(); i++)
if(coc != par){
don += dfs(coc, node);
if(s[coc].size() > s[node].size())
swap(s[node], s[coc]);
for(it = s[coc].begin(); it != s[coc].end(); it++)
s[node].insert(*it);
}
s[node].insert(a[node]);
for(int i = 0; i < cik[node].size(); i++)
s[node].erase(cik[node][i]);
if(!don and s[node].empty() and par and (fl or !amk) ){
amk = node;
of = par;
don = 1;
ans++;
}
return don;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d %d",&n ,&k);
for(int i = 1; i < n; i++){
int u, v;
scanf("%d %d",&u ,&v);
g[v].pb(u);
g[u].pb(v);
}
for(int i = 1; i <= n; i++)
scanf("%d",a + i);
hazirla(1, 0, 1);
for(int i = 1; i <= LOGN; i++)
for(int j = 1; j <= n; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
for(int i = 1; i <= n; i++){
l[a[i]] = lca(l[a[i]], i);
}
for(int i = 1; i <= k; i++)
cik[l[i]].pb(i);
dfs(1, 0);
for(int i = 1; i <= n; i++){
l[i] = 0;
cik[i].clear();
s[i].clear();
}
fl = 1;
ans = 0;
// cout << amk << " " << of << endl;
hazirla(amk, 0, 1);
for(int i = 1; i <= LOGN; i++)
for(int j = 1; j <= n; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
for(int i = 1; i <= n; i++){
l[a[i]] = lca(l[a[i]], i);
}
for(int i = 1; i <= k; i++)
cik[l[i]].pb(i);
dfs(amk, 0);
printf("%d",ans);
return 0;
}
Compilation message
mergers.cpp: In function 'void hazirla(int, int, int)':
mergers.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
mergers.cpp: In function 'int dfs(int, int)':
mergers.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
mergers.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cik[node].size(); i++)
~~^~~~~~~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n ,&k);
~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&u ,&v);
~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",a + i);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
94460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
94460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
94460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
111984 KB |
Output is correct |
| 2 |
Incorrect |
252 ms |
110580 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
94460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
