| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 919349 | imarn | Mergers (JOI19_mergers) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=5e5+5;
vector<int>g[N],gg[N];
int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
void push(int i,int l,int r){
if(lz[i]==1e9)return;
t[i]=min(t[i],lz[i]);
if(l<r){
lz[2*i]=min(lz[2*i],lz[i]);
lz[2*i+1]=min(lz[2*i+1],lz[i]);
}lz[i]=1e9;
}
void upd(int i,int l,int r,int tl,int tr,int id){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]=min(lz[i],id);push(i,l,r);
return;
}int m=(l+r)>>1;
upd(2*i,l,m,tl,tr,id);upd(2*i+1,m+1,r,tl,tr,id);
t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
push(i,l,r);
if(r<tl||l>tr)return 1e9;
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
void update(int x,int y,int z){
while(head[x]!=head[y]){
if(dep[head[x]]<dep[head[y]])swap(x,y);
upd(1,1,n,id[head[x]],id[x],z);
x=pr[head[x]];
}if(dep[x]>dep[y])swap(x,y);
upd(1,1,n,id[x],id[y],z);
}
int query(int x,int y,int res=1e9){
while(head[x]!=head[y]){
if(dep[head[x]]<dep[head[y]])swap(x,y);
res=min(qr(1,1,n,id[head[x]],id[x]),res);
x=pr[head[x]];
}if(dep[x]>dep[y])swap(x,y);
res=min(res,qr(1,1,n,id[x],id[y]));return res;
}
void dfssz(int u,int p,int l){
sz[u]=1;dep[u]=l;pr[u]=p;
for(auto v:g[u]){
if(v==p)continue;dfssz(v,u,l+1);
sz[u]+=sz[v];
}
}
void hld(int u,int p,int tp){
head[u]=tp;id[u]=++cur;
int hc=-1,hv=-1;
for(auto v:g[u]){
if(v==p)continue;
if(sz[v]>hc)hv=v,hc=sz[v];
}if(hv==-1)return;
hld(hv,u,tp);
for(auto v:g[u]){
if(v==p||v==hv)continue;
hld(v,u,v);
}
}vector<int>gr[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int k;cin>>n>>k;
for(int i=0;i<4*N;i++)t[i]=lz[i]=1e9;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
}dfssz(1,1,0);hld(1,1,1);
for(int i=1,x;i<=n;i++)cin>>x,gr[x].pb(i);
for(int i=1;i<=k;i++){
if(gr[i].empty())continue;
int top=gr[i][0];int res=cp;
for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
for(int j=0;j<gr[i].size();j++)update(top,gr[i][j],res);
cp++;
}for(int i=1;i<=n;i++)pos[i]=qr(1,1,n,id[i],id[i]);
for(int i=1;i<=n;i++){
for(auto v:g[i]){
if(pos[v]==pos[i])continue;
gg[pos[v]].pb(pos[i]);
gg[pos[i]].pb(pos[v]);
}
}int ct=0;
for(int i=1;i<=n;i++){
if(gg[i].empty())continue;
sort(gg[i].begin(),gg[i].end());
gg[i].erase(unique(gg[i].begin(),gg[i].end()),gg[i].end());
if(gg[i].size()==1)ct++;
}cout<<(ct+1)/2;
}
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int N=5e5+5;
vector<int>g[N],gg[N];
int sz[N],id[N],pr[N],head[N],dep[N],cur=0,t[4*N],lz[4*N],pos[N],cp=1,n;
void push(int i,int l,int r){
if(lz[i]==1e9)return;
t[i]=min(t[i],lz[i]);
if(l<r){
lz[2*i]=min(lz[2*i],lz[i]);
lz[2*i+1]=min(lz[2*i+1],lz[i]);
}lz[i]=1e9;
}
void upd(int i,int l,int r,int tl,int tr,int id){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]=min(lz[i],id);push(i,l,r);
return;
}int m=(l+r)>>1;
upd(2*i,l,m,tl,tr,id);upd(2*i+1,m+1,r,tl,tr,id);
t[i]=min(t[2*i],t[2*i+1]);
}
int qr(int i,int l,int r,int tl,int tr){
push(i,l,r);
if(r<tl||l>tr)return 1e9;
if(r<=tr&&l>=tl)return t[i];
int m=(l+r)>>1;
return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
}
void update(int x,int y,int z){
while(head[x]!=head[y]){
if(dep[head[x]]<dep[head[y]])swap(x,y);
upd(1,1,n,id[head[x]],id[x],z);
x=pr[head[x]];
}if(dep[x]>dep[y])swap(x,y);
upd(1,1,n,id[x],id[y],z);
}
int query(int x,int y,int res=1e9){
while(head[x]!=head[y]){
if(dep[head[x]]<dep[head[y]])swap(x,y);
res=min(qr(1,1,n,id[head[x]],id[x]),res);
x=pr[head[x]];
}if(dep[x]>dep[y])swap(x,y);
res=min(res,qr(1,1,n,id[x],id[y]));return res;
}
void dfssz(int u,int p,int l){
sz[u]=1;dep[u]=l;pr[u]=p;
for(auto v:g[u]){
if(v==p)continue;dfssz(v,u,l+1);
sz[u]+=sz[v];
}
}
void hld(int u,int p,int tp){
head[u]=tp;id[u]=++cur;
int hc=-1,hv=-1;
for(auto v:g[u]){
if(v==p)continue;
if(sz[v]>hc)hv=v,hc=sz[v];
}if(hv==-1)return;
hld(hv,u,tp);
for(auto v:g[u]){
if(v==p||v==hv)continue;
hld(v,u,v);
}
}vector<int>gr[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int k;cin>>n>>k;
for(int i=0;i<4*N;i++)t[i]=lz[i]=1e9;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
}dfssz(1,1,0);hld(1,1,1);
for(int i=1,x;i<=n;i++)cin>>x,gr[x].pb(i);
for(int i=1;i<=k;i++){
if(gr[i].empty())continue;
int top=gr[i][0];int res=cp;
for(int j=0;j<gr[i].size();j++)res=min(res,query(top,gr[i][j]));
for(int j=0;j<gr[i].size();j++)update(top,gr[i][j],res);
cp++;
}for(int i=1;i<=n;i++)pos[i]=qr(1,1,n,id[i],id[i]);
for(int i=1;i<=n;i++){
for(auto v:g[i]){
if(pos[v]==pos[i])continue;
gg[pos[v]].pb(pos[i]);
gg[pos[i]].pb(pos[v]);
}
}int ct=0;
for(int i=1;i<=n;i++){
if(gg[i].empty())continue;
sort(gg[i].begin(),gg[i].end());
gg[i].erase(unique(gg[i].begin(),gg[i].end()),gg[i].end());
if(gg[i].size()==1)ct++;
}cout<<(ct+1)/2;
}