| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 118407 | kig9981 | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int SZ=1<<17;
vector<int> adj[100000];
int N, parent[100000], W[100000], num[100000], R[100000], hld[100000], V[100000], tree[2*SZ][4];
void add_tree(int n, int v1, int v2)
{
n+=SZ;
tree[n][0]+=v1; tree[n][3]+=v2;
while(n>>=1) {
for(int i=0;i<4;i++) tree[n][i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) tree[n][(i&2)|(j&1)]=min(tree[n][(i&2)|(j&1)],tree[2*n][i]+tree[2*n+1][j]+((i&1)^(j>>1)));
}
}
void get_ans(int *ret, int s, int e)
{
int r1[4]={0,0x1fffffff,0x1fffffff,0}, r2[4]={0,0x1fffffff,0x1fffffff,0};
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) {
for(int i=0;i<4;i++) ret[i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],r1[i]+tree[s][j]+((i&1)^(j>>1)));
for(int i=0;i<4;i++) r1[i]=ret[i];
s++;
}
if(~e&1) {
for(int i=0;i<4;i++) ret[i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],tree[e][i]+r2[j]+((i&1)^(j>>1)));
for(int i=0;i<4;i++) r2[i]=ret[i];
e--;
}
}
for(int i=0;i<4;i++) ret[i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],r1[i]+r2[j]+((i&1)^(j>>1)));
}
int dfs(int c)
{
W[c]=1;
for(auto n: adj[c]) if(W[n]==0) {
parent[n]=c;
W[c]+=dfs(n);
}
return W[c];
}
int dfs2(int c)
{
num[c]=R[c]=N++;
for(auto n: adj[c]) if(parent[n]==c && 2*W[n]>=W[c]) {
hld[n]=hld[c];
R[c]=dfs2(n);
}
for(auto n: adj[c]) if(parent[n]==c && 2*W[n]<W[c]) {
hld[n]=n;
dfs2(n);
}
return R[c];
}
void initialize(int N, vector<int> A, vector<int> B)
{
for(int i=0;i<N-1;i++) {
adj[--A[i]].push_back(--B[i]);
adj[B[i]].push_back(A[i]);
tree[SZ+i][1]=tree[SZ+i][2]=N;
}
tree[SZ+N-1][1]=tree[SZ+N-1][2]=N;
dfs(0); dfs2(0);
}
int cat(int c)
{
int t1[4], t2[4], v1=0, v2=N;
V[--c]=1;
for(;;) {
get_ans(t1,num[hld[c]],R[c]);
add_tree(num[c],v1,v2);
get_ans(t2,num[hld[c]],R[c]);
if(hld[c]==0) break;
v1=min(t2[0],t2[1])-min(t1[0],t1[1]);
v2=min(t2[2],t2[3])-min(t1[2],t1[3]);
c=parent[hld[c]];
}
return min({t2[0],t2[1],t2[2],t2[3]});
}
int dog(int c)
{
int t1[4], t2[4], v1=N, v2=0;
V[--c]=2;
for(;;) {
get_ans(t1,num[hld[c]],R[c]);
add_tree(num[c],v1,v2);
get_ans(t2,num[hld[c]],R[c]);
if(hld[c]==0) break;
v1=min(t2[0],t2[1])-min(t1[0],t1[1]);
v2=min(t2[2],t2[3])-min(t1[2],t1[3]);
c=parent[hld[c]];
}
return min({t2[0],t2[1],t2[2],t2[3]});
}
int neighbor(int c)
{
c--;
int t1[4], t2[4], v1=-N*(V[c]==2), v2=-N*(V[c]==1);
V[c]=0;
for(;;) {
get_ans(t1,num[hld[c]],R[c]);
add_tree(num[c],v1,v2);
get_ans(t2,num[hld[c]],R[c]);
if(hld[c]==0) break;
v1=min(t2[0],t2[1])-min(t1[0],t1[1]);
v2=min(t2[2],t2[3])-min(t1[2],t1[3]);
c=parent[hld[c]];
}
return min({t2[0],t2[1],t2[2],t2[3]});
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, Q;
vector<int> A, B;
cin>>N;
A.resize(N-1); B.resize(N-1);
for(int i=0;i<N-1;i++) cin>>A[i]>>B[i];
initialize(N,A,B);
for(cin>>Q;Q--;) {
int t, v;
cin>>t>>v;
if(t==1) cout<<cat(v)<<'\n';
else if(t==2) cout<<dog(v)<<'\n';
else cout<<neighbor(v)<<'\n';
}
return 0;
}