oj.uz

Submission #118408

# Submission time Handle Problem Language Result Execution time Memory
118408 2019-06-19T00:53:41 Z kig9981 Cats or Dogs (JOI18_catdog) C++17
0 / 100
 4 ms 2816 KB 
#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]});
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -