oj.uz

답안 #781857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781857 2023-07-13T12:03:02 Z kshitij_sodani Cats or Dogs (JOI18_catdog) C++14
100 / 100
 592 ms 109020 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
//#define endl '\n'


#include "catdog.h"

llo x;
vector<llo> adj[100001];
llo dp[100001][2];
llo it[100001];
llo par[100001];
llo ss[100001];
llo st[100001];
llo par3[100001];
llo n;
vector<vector<vector<llo>>> tree[100001];
vector<llo> pre[100001];

void dfs(llo no,llo par2=-1){
	ss[no]=1;
	par[no]=par2;
	vector<pair<llo,llo>> tt;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
			tt.pb({ss[j],j});
			ss[no]+=ss[j];
		}
	}
	sort(tt.begin(),tt.end());
	adj[no].clear();
	while(tt.size()){
		adj[no].pb(tt.back().b);
		tt.pop_back();
	}
}
llo co=0;

void dfs2(llo no,llo par2=-1){
	par3[no]=no;
	st[no]=co;
	co++;
	if(par2!=-1){
		if(st[no]==st[par2]+1){
			par3[no]=par3[par2];
		}
	}
//	ind[no]=pre[par3[no]].size();
	pre[par3[no]].pb(no);
	vector<llo> kk;
	kk.pb(0);
	kk.pb(0);
	vector<vector<llo>> ll;
	ll.pb(kk);
	ll.pb(kk);
	for(llo i=0;i<4;i++){
		tree[par3[no]].pb(ll);
	}
	for(auto j:adj[no]){
		if(j!=par2){
			dfs2(j,no);
		}
	}
}
void build(llo ind,llo no,llo l,llo r){
	if(l==r){
		tree[ind][no][0][0]=0;
		tree[ind][no][1][1]=0;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;
	}
	else{
		llo mid=(l+r)/2;
		build(ind,no*2+1,l,mid);
		build(ind,no*2+2,mid+1,r);
		tree[ind][no][0][0]=0;
		tree[ind][no][1][1]=0;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;		/*for(llo i=0;i<2;i++){
			for(llo j=0;j<2;j++){
				for(llo l=0;l<2;l++){
					for(llo k=0;k<2;k++){
						llo x=1;
						if(j==l){
							x=0;
						}
						tree[ind][no][i][k]=min(tree[ind][no][i][k],tree[ind][no*2+1][i][j]+tree[ind][no*2+2][l][k]+x);
					}
				}
			}
		}*/

	}
}
void update(llo ind,llo no,llo l,llo r,llo i,llo j){
	if(l==r){
		tree[ind][no][0][0]=dp[j][0];
		tree[ind][no][1][1]=dp[j][1];
		if(it[j]==2){
			//cout<<22<<endl;
			tree[ind][no][0][0]=1e6;
		}
		if(it[j]==1){

			tree[ind][no][1][1]=1e6;
		}
	//	cout<<j<<","<<tree[ind][no][0][0]<<","<<tree[ind][no][1][1]<<endl;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(ind,no*2+1,l,mid,i,j);
		}
		else{
			update(ind,no*2+2,mid+1,r,i,j);
		}
		tree[ind][no][0][0]=1e6;
		tree[ind][no][1][1]=1e6;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;
		for(llo ii=0;ii<2;ii++){
			for(llo jj=0;jj<2;jj++){
				for(llo l=0;l<2;l++){
					for(llo k=0;k<2;k++){
						llo x=0;
						if(jj!=l){
							x++;
						}
						/*if(j==6 and no==0 and  tree[ind][no*2+1][ii][jj]+tree[ind][no*2+2][l][k]+x==0){
							cout<<1111<<endl;
							cout<<ii<<":"<<jj<<":"<<l<<":"<<k<<endl;
						}*/
						tree[ind][no][ii][k]=min(tree[ind][no][ii][k],tree[ind][no*2+1][ii][jj]+tree[ind][no*2+2][l][k]+x);
					}
				}
			}
		}
	/*	if(no==0){
			cout<<tree[ind][no*2+1][0][0]<<"?"<<tree[ind][no*2+2][1][1]<<endl;
		}*/

	}
	/*cout<<no<<":"<<l<<":"<<r<<endl;
	for(int ii=0;ii<2;ii++){
		for(int jj=0;jj<2;jj++){
			cout<<tree[ind][no][ii][jj]<<"<";
		}
		cout<<endl;
	}*/
}
void initialize(int nn, std::vector<int> aa, std::vector<int> bb) {
	n=nn;
	for(llo i=0;i<n-1;i++){
		adj[aa[i]-1].pb(bb[i]-1);
		adj[bb[i]-1].pb(aa[i]-1);
	}
	dfs(0);
	dfs2(0);
	for(llo i=0;i<n;i++){
		if(pre[i].size()){
			build(i,0,0,pre[i].size()-1);
		}
	}
	for(llo i=0;i<n;i++){
		it[i]=0;
		dp[i][0]=0;
		dp[i][1]=0;
	}
}
void apply(llo i){
	//<llo> xx;
 	llo cur=i;
 	while(true){
 		cur=par3[cur];
 		if(cur==0){
 			break;
 		}
 		dp[par[cur]][0]-=min(min(tree[cur][0][0][0],tree[cur][0][0][1]),min(tree[cur][0][1][0],tree[cur][0][1][1])+1);
 		dp[par[cur]][1]-=min(min(tree[cur][0][0][0],tree[cur][0][0][1])+1,min(tree[cur][0][1][0],tree[cur][0][1][1]));
 		cur=par[cur];
 	}
 	update(par3[i],0,0,pre[par3[i]].size()-1,st[i]-st[par3[i]],i);
 //	cout<<i<<"::"<<par3[i]<<endl;
 //	cout<<st[i]-st[par3[i]]<<endl;
 	cur=i;
 	while(true){
 		cur=par3[cur];
 		if(cur==0){
 			break;
 		}
 		dp[par[cur]][0]+=min(min(tree[cur][0][0][0],tree[cur][0][0][1]),min(tree[cur][0][1][0],tree[cur][0][1][1])+1);
 		dp[par[cur]][1]+=min(min(tree[cur][0][0][0],tree[cur][0][0][1])+1,min(tree[cur][0][1][0],tree[cur][0][1][1]));
 		cur=par[cur];
 	//	cout<<11<<endl;
 		update(par3[cur],0,0,pre[par3[cur]].size()-1,st[cur]-st[par3[cur]],cur);
 	}
}
int cat(int i) {
	i--;
	it[i]=1;
	apply(i);
 	//dp[i][1]=1e6;
 //	dfs(0);
 	llo ans=1e6;
 	for(llo i=0;i<2;i++){
 		for(llo j=0;j<2;j++){
 			ans=min(ans,tree[0][0][i][j]);
 		}
 	}
 /*	for(llo i=0;i<n;i++){
 		cout<<dp[i][0]<<","<<dp[i][1]<<endl;
 	}*/
 //	cout<<ans<<endl;
	return ans;
}

int dog(int i) {
	i--;
	it[i]=2;
	apply(i);
 	llo ans=1e6;
 //	cout<<dp[0][0]<<":"<<dp[0][1]<<endl;
 //	cout<<tree[0][0][0][1]<<":::"<<endl;
  	//	cout<<par3[i]<<"::"<<endl;
 	for(llo i=0;i<2;i++){
 		for(llo j=0;j<2;j++){
 			ans=min(ans,tree[0][0][i][j]);
 			//<<tree[0][0][i][j]<<",,";
 		}
 		//cout<<endl;
 	}

 /*	for(llo i=0;i<n;i++){
 		cout<<dp[i][0]<<","<<dp[i][1]<<endl;
 	}*/
 	//cout<<ans<<endl;

	return ans;
}

int neighbor(int i) {
	i--;
	it[i]=0;
	apply(i);
 	llo ans=1e6;
 	for(llo i=0;i<2;i++){
 		for(llo j=0;j<2;j++){
 			ans=min(ans,tree[0][0][i][j]);
 		}
 	}

 	/*for(llo i=0;i<n;i++){
 		cout<<dp[i][0]<<","<<dp[i][1]<<endl;
 	}*/
 	//cout<<ans<<endl;
	return ans;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7356 KB Output is correct
2 Correct 6 ms 7388 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 24 ms 7280 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 6 ms 7392 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7396 KB Output is correct
11 Correct 4 ms 7344 KB Output is correct
12 Correct 5 ms 7356 KB Output is correct
13 Correct 5 ms 7384 KB Output is correct
14 Correct 4 ms 7368 KB Output is correct
15 Correct 5 ms 7284 KB Output is correct
16 Correct 5 ms 7356 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7356 KB Output is correct
2 Correct 6 ms 7388 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 24 ms 7280 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 6 ms 7392 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7396 KB Output is correct
11 Correct 4 ms 7344 KB Output is correct
12 Correct 5 ms 7356 KB Output is correct
13 Correct 5 ms 7384 KB Output is correct
14 Correct 4 ms 7368 KB Output is correct
15 Correct 5 ms 7284 KB Output is correct
16 Correct 5 ms 7356 KB Output is correct
17 Correct 6 ms 7892 KB Output is correct
18 Correct 6 ms 8100 KB Output is correct
19 Correct 5 ms 7880 KB Output is correct
20 Correct 4 ms 7508 KB Output is correct
21 Correct 6 ms 7508 KB Output is correct
22 Correct 7 ms 7616 KB Output is correct
23 Correct 8 ms 8016 KB Output is correct
24 Correct 5 ms 7880 KB Output is correct
25 Correct 5 ms 7636 KB Output is correct
26 Correct 6 ms 7636 KB Output is correct
27 Correct 6 ms 7620 KB Output is correct
28 Correct 6 ms 8008 KB Output is correct
29 Correct 7 ms 8188 KB Output is correct
30 Correct 5 ms 7488 KB Output is correct
31 Correct 4 ms 7892 KB Output is correct
32 Correct 4 ms 7624 KB Output is correct

Subtask #3
62.0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7356 KB Output is correct
2 Correct 6 ms 7388 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 24 ms 7280 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 6 ms 7392 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7396 KB Output is correct
11 Correct 4 ms 7344 KB Output is correct
12 Correct 5 ms 7356 KB Output is correct
13 Correct 5 ms 7384 KB Output is correct
14 Correct 4 ms 7368 KB Output is correct
15 Correct 5 ms 7284 KB Output is correct
16 Correct 5 ms 7356 KB Output is correct
17 Correct 6 ms 7892 KB Output is correct
18 Correct 6 ms 8100 KB Output is correct
19 Correct 5 ms 7880 KB Output is correct
20 Correct 4 ms 7508 KB Output is correct
21 Correct 6 ms 7508 KB Output is correct
22 Correct 7 ms 7616 KB Output is correct
23 Correct 8 ms 8016 KB Output is correct
24 Correct 5 ms 7880 KB Output is correct
25 Correct 5 ms 7636 KB Output is correct
26 Correct 6 ms 7636 KB Output is correct
27 Correct 6 ms 7620 KB Output is correct
28 Correct 6 ms 8008 KB Output is correct
29 Correct 7 ms 8188 KB Output is correct
30 Correct 5 ms 7488 KB Output is correct
31 Correct 4 ms 7892 KB Output is correct
32 Correct 4 ms 7624 KB Output is correct
33 Correct 319 ms 46824 KB Output is correct
34 Correct 194 ms 56588 KB Output is correct
35 Correct 193 ms 34036 KB Output is correct
36 Correct 457 ms 76456 KB Output is correct
37 Correct 56 ms 30192 KB Output is correct
38 Correct 539 ms 84688 KB Output is correct
39 Correct 592 ms 84696 KB Output is correct
40 Correct 492 ms 84640 KB Output is correct
41 Correct 479 ms 84696 KB Output is correct
42 Correct 573 ms 84728 KB Output is correct
43 Correct 525 ms 84676 KB Output is correct
44 Correct 470 ms 84604 KB Output is correct
45 Correct 588 ms 84732 KB Output is correct
46 Correct 480 ms 84712 KB Output is correct
47 Correct 509 ms 84716 KB Output is correct
48 Correct 163 ms 62892 KB Output is correct
49 Correct 170 ms 78168 KB Output is correct
50 Correct 38 ms 21048 KB Output is correct
51 Correct 67 ms 34696 KB Output is correct
52 Correct 32 ms 21512 KB Output is correct
53 Correct 365 ms 83000 KB Output is correct
54 Correct 164 ms 39332 KB Output is correct
55 Correct 380 ms 59516 KB Output is correct
56 Correct 184 ms 41788 KB Output is correct
57 Correct 333 ms 76124 KB Output is correct
58 Correct 61 ms 39340 KB Output is correct
59 Correct 62 ms 31912 KB Output is correct
60 Correct 150 ms 69796 KB Output is correct
61 Correct 152 ms 72256 KB Output is correct
62 Correct 116 ms 60400 KB Output is correct
63 Correct 112 ms 54708 KB Output is correct
64 Correct 155 ms 60588 KB Output is correct
65 Correct 248 ms 92624 KB Output is correct
66 Correct 73 ms 26368 KB Output is correct
67 Correct 159 ms 66536 KB Output is correct
68 Correct 287 ms 95596 KB Output is correct
69 Correct 39 ms 13364 KB Output is correct
70 Correct 9 ms 8140 KB Output is correct
71 Correct 117 ms 46252 KB Output is correct
72 Correct 182 ms 80992 KB Output is correct
73 Correct 299 ms 109020 KB Output is correct
74 Correct 340 ms 95236 KB Output is correct
75 Correct 267 ms 108564 KB Output is correct
76 Correct 312 ms 98064 KB Output is correct
77 Correct 330 ms 95252 KB Output is correct