oj.uz

Submission #160857

# Submission time Handle Problem Language Result Execution time Memory
160857 2019-10-30T11:46:03 Z gs18115 Cats or Dogs (JOI18_catdog) C++14
100 / 100
 927 ms 25592 KB 
#include"catdog.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
struct co
{
	int v[2][2];
	co(int x=0,int y=0,int z=0,int w=0)
	{
		v[0][0]=x;
		v[0][1]=y;
		v[1][0]=z;
		v[1][1]=w;
	}
	inline co operator^(const co&x)const
	{
		if(v[0][0]==-inf)
			return x;
		if(x.v[0][0]==-inf)
			return*this;
		co ret;
		int i,j,k,l;
		for(i=0;i<2;i++)
			for(j=0;j<2;j++)
				ret.v[i][j]=inf;
		for(i=0;i<2;i++)
			for(j=0;j<2;j++)	
				for(k=0;k<2;k++)
					for(l=0;l<2;l++)
						ret.v[i][l]=min(ret.v[i][l],v[i][j]+x.v[k][l]+(j==k?0:1));
		return ret;
	}
};
struct seg
{
	co t[400010];
	void init(int n,int s,int e)
	{
		if(s==e)
		{
			t[n]=co(0,inf,inf,0);
			return;
		}
		int m=s+e>>1;
		init(n*2,s,m);
		init(n*2+1,m+1,e);
		t[n]=t[n*2]^t[n*2+1];
		return;
	}
	void si(int n,int s,int e,int x,pi p)
	{
		if(s==e)
		{
			t[n].v[0][0]+=p.fi;
			t[n].v[1][1]+=p.se;
			return;
		}
		int m=s+e>>1;
		if(x>m)
			si(n*2+1,m+1,e,x,p);
		else
			si(n*2,s,m,x,p);
		t[n]=t[n*2]^t[n*2+1];
		return;
	}
	co sq(int n,int s,int e,int S,int E)
	{
		if(s>E||S>e)
			return co(-inf);
		if(S<=s&&e<=E)
			return t[n];
		int m=s+e>>1;
		return sq(n*2,s,m,S,E)^sq(n*2+1,m+1,e,S,E);
	}
}st;
vector<int>adj[100010];
int pa[100010];
int sz[100010];
void dfs(int x)
{
	sz[x]=1;
	for(int t:adj[x])
	{
		adj[t].erase(find(all(adj[t]),x));
		pa[t]=x;
		dfs(t);
		sz[x]+=sz[t];
	}
	sort(all(adj[x]),[=](const int&x,const int&y){return sz[x]>sz[y];});
	return;
}
int in[100010];
int cn;
int chn[100010];
int top[100010],bot[100010];
int cct;
void hld(int x)
{
	in[x]=++cn;
	if(adj[x].empty())
	{
		bot[chn[x]]=x;
		return;
	}
	int&f=adj[x][0];
	chn[f]=chn[x];
	hld(f);
	for(int i=1;i<adj[x].size();i++)
	{
		int&t=adj[x][i];
		chn[t]=++cct;
		top[cct]=t;
		hld(t);
	}
	return;
}
int n;
inline void upd(int x,pi p)
{
	while(x>0)
	{
		co cu=st.sq(1,1,n,in[top[chn[x]]],in[bot[chn[x]]]);
		st.si(1,1,n,in[x],p);
		co rt=st.sq(1,1,n,in[top[chn[x]]],in[bot[chn[x]]]);
		int c0=min(cu.v[0][0],cu.v[0][1]);
		int c1=min(cu.v[1][0],cu.v[1][1]);
		int t0=min(rt.v[0][0],rt.v[0][1]);
		int t1=min(rt.v[1][0],rt.v[1][1]);
		p=pi(min(t0,t1+1)-min(c0,c1+1),min(t1,t0+1)-min(c1,c0+1));
		x=pa[top[chn[x]]];
	}
	return;
}
inline int ans()
{
	co a=st.sq(1,1,n,1,in[bot[0]]);
	return min({a.v[0][0],a.v[0][1],a.v[1][0],a.v[1][1]});
}
void initialize(int N,vector<int>A,vector<int>B)
{
	n=N;
	for(int i=0;i<n-1;i++)
		adj[A[i]].eb(B[i]),adj[B[i]].eb(A[i]);
	dfs(1);
	top[0]=1;
	hld(1);
	st.init(1,1,n);
	return;
}
bool tp[100010];
int cat(int v)
{
	tp[v]=0;
	upd(v,pi(0,inf));
	return ans();
}
int dog(int v)
{
	tp[v]=1;
	upd(v,pi(inf,0));
	return ans();
}
int neighbor(int v)
{
	upd(v,tp[v]?pi(-inf,0):pi(0,-inf));
	return ans();
}

Compilation message

catdog.cpp: In member function 'void seg::init(int, int, int)':
catdog.cpp:55:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
catdog.cpp: In member function 'void seg::si(int, int, int, int, pi)':
catdog.cpp:69:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
catdog.cpp: In member function 'co seg::sq(int, int, int, int, int)':
catdog.cpp:83:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
catdog.cpp: In function 'void hld(int)':
catdog.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<adj[x].size();i++)
              ~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 9 ms 8952 KB Output is correct
4 Correct 11 ms 8924 KB Output is correct
5 Correct 9 ms 8952 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 9080 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 9 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 10 ms 8952 KB Output is correct
12 Correct 9 ms 8952 KB Output is correct
13 Correct 9 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 9 ms 8952 KB Output is correct
16 Correct 10 ms 8952 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 9 ms 8952 KB Output is correct
4 Correct 11 ms 8924 KB Output is correct
5 Correct 9 ms 8952 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 9080 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 9 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 10 ms 8952 KB Output is correct
12 Correct 9 ms 8952 KB Output is correct
13 Correct 9 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 9 ms 8952 KB Output is correct
16 Correct 10 ms 8952 KB Output is correct
17 Correct 11 ms 8952 KB Output is correct
18 Correct 12 ms 9080 KB Output is correct
19 Correct 11 ms 8952 KB Output is correct
20 Correct 10 ms 8952 KB Output is correct
21 Correct 10 ms 8952 KB Output is correct
22 Correct 10 ms 8952 KB Output is correct
23 Correct 12 ms 9052 KB Output is correct
24 Correct 12 ms 9080 KB Output is correct
25 Correct 11 ms 8952 KB Output is correct
26 Correct 10 ms 8952 KB Output is correct
27 Correct 10 ms 8952 KB Output is correct
28 Correct 10 ms 9080 KB Output is correct
29 Correct 20 ms 9084 KB Output is correct
30 Correct 10 ms 9080 KB Output is correct
31 Correct 10 ms 8952 KB Output is correct
32 Correct 11 ms 9080 KB Output is correct

Subtask #3
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 9 ms 8952 KB Output is correct
4 Correct 11 ms 8924 KB Output is correct
5 Correct 9 ms 8952 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 9080 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 9 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 10 ms 8952 KB Output is correct
12 Correct 9 ms 8952 KB Output is correct
13 Correct 9 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 9 ms 8952 KB Output is correct
16 Correct 10 ms 8952 KB Output is correct
17 Correct 11 ms 8952 KB Output is correct
18 Correct 12 ms 9080 KB Output is correct
19 Correct 11 ms 8952 KB Output is correct
20 Correct 10 ms 8952 KB Output is correct
21 Correct 10 ms 8952 KB Output is correct
22 Correct 10 ms 8952 KB Output is correct
23 Correct 12 ms 9052 KB Output is correct
24 Correct 12 ms 9080 KB Output is correct
25 Correct 11 ms 8952 KB Output is correct
26 Correct 10 ms 8952 KB Output is correct
27 Correct 10 ms 8952 KB Output is correct
28 Correct 10 ms 9080 KB Output is correct
29 Correct 20 ms 9084 KB Output is correct
30 Correct 10 ms 9080 KB Output is correct
31 Correct 10 ms 8952 KB Output is correct
32 Correct 11 ms 9080 KB Output is correct
33 Correct 443 ms 14392 KB Output is correct
34 Correct 140 ms 14328 KB Output is correct
35 Correct 401 ms 13296 KB Output is correct
36 Correct 680 ms 17856 KB Output is correct
37 Correct 32 ms 11384 KB Output is correct
38 Correct 765 ms 18612 KB Output is correct
39 Correct 731 ms 18612 KB Output is correct
40 Correct 753 ms 18664 KB Output is correct
41 Correct 927 ms 18664 KB Output is correct
42 Correct 805 ms 18624 KB Output is correct
43 Correct 695 ms 18668 KB Output is correct
44 Correct 644 ms 18600 KB Output is correct
45 Correct 688 ms 18628 KB Output is correct
46 Correct 811 ms 18660 KB Output is correct
47 Correct 702 ms 18580 KB Output is correct
48 Correct 214 ms 16320 KB Output is correct
49 Correct 241 ms 18080 KB Output is correct
50 Correct 82 ms 11128 KB Output is correct
51 Correct 94 ms 12548 KB Output is correct
52 Correct 44 ms 10744 KB Output is correct
53 Correct 292 ms 17272 KB Output is correct
54 Correct 227 ms 12844 KB Output is correct
55 Correct 591 ms 16196 KB Output is correct
56 Correct 341 ms 13716 KB Output is correct
57 Correct 465 ms 17128 KB Output is correct
58 Correct 45 ms 12660 KB Output is correct
59 Correct 89 ms 12380 KB Output is correct
60 Correct 202 ms 17156 KB Output is correct
61 Correct 213 ms 17520 KB Output is correct
62 Correct 137 ms 15624 KB Output is correct
63 Correct 74 ms 15736 KB Output is correct
64 Correct 84 ms 17400 KB Output is correct
65 Correct 101 ms 22008 KB Output is correct
66 Correct 112 ms 12792 KB Output is correct
67 Correct 113 ms 18296 KB Output is correct
68 Correct 316 ms 22572 KB Output is correct
69 Correct 59 ms 10488 KB Output is correct
70 Correct 20 ms 9208 KB Output is correct
71 Correct 95 ms 15500 KB Output is correct
72 Correct 145 ms 20600 KB Output is correct
73 Correct 323 ms 25592 KB Output is correct
74 Correct 372 ms 22136 KB Output is correct
75 Correct 249 ms 25592 KB Output is correct
76 Correct 258 ms 24312 KB Output is correct
77 Correct 380 ms 22520 KB Output is correct