답안 #97795 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97795	2019-02-18T14:02:24 Z	fefe	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3000 ms	26780 KB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
#define MAX_N 200005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 1000005
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int x;
struct node{
	int cost[4];
}tree[4*MAX_N];
int n,m;
int num[MAX_N],sta[MAX_N],cnt[MAX_N],pa[MAX_N];
bool vis[MAX_N];
vector<int> E[MAX_N],lst[MAX_N];
void make_HLD(int x){
	cnt[x]=1;
	if(x!=1 && E[x].size()==1){
		E[x][0]=0;
		lst[m].pb(x);
		num[x]=m++;
		return;
	}
	int mi=0;
	for(int &y:E[x]){
		if(cnt[y]){y=0;continue;}
		make_HLD(y);pa[y]=x;
		cnt[x]+=cnt[y];
		if(cnt[y]>cnt[mi])	mi=y;
	}
	num[x]=num[mi];
	lst[num[x]].pb(x);
}
void init1(int x){for(int i=0;i<4;i++)	tree[x].cost[i]=(i%3?1:0)*inf;}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
	cnt[0]=-1;
	n=N;
	for(int i=0;i<n-1;i++){
		E[A[i]].pb(B[i]);
		E[B[i]].pb(A[i]);
	}
	make_HLD(1);
	int x=n;
	for(int i=0;i<m;i++){
		for(int j:lst[i]){cnt[j]=x--;}
	}
	for(int i=1;i<=4*n;i++)	init1(i);
}
node merge(node x,node y){
	node p;
	for(int i=0;i<4;i++)	p.cost[i]=inf;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++)	p.cost[(i/2)*2+j%2]=min(p.cost[(i/2)*2+j%2],x.cost[i]+y.cost[j]+((i%2)^(j/2)));
	}
	return p;
}
void udt_tree(int x,int l,int r,int p,node v){
	if(p<l || r<p)	return;
	if(l==r){
		tree[x]=v;
		return;
	}
	int mid=(l+r)>>1;
	udt_tree(2*x,l,mid,p,v);
	udt_tree(2*x+1,mid+1,r,p,v);
	tree[x]=merge(tree[2*x],tree[2*x+1]);
}
node get_cost(int x,int l,int r,int s,int e){
	if(e<l || s>r)	return {0,inf,inf,0};
	if(s<=l && r<=e)	return tree[x];
	int mid=(l+r)>>1;
	return merge(get_cost(2*x,l,mid,s,e),get_cost(2*x+1,mid+1,r,s,e));
}
node get_v(int x){
	int c=0,d=0;
	for(int y:E[x]){
		if(!y || num[y]==num[x])	continue;
		node p=get_cost(1,1,n,cnt[y],cnt[lst[num[y]][0]]);
		p.cost[0]=min(p.cost[0],p.cost[1]);
		p.cost[1]=min(p.cost[2],p.cost[3]);
		c+=min(p.cost[0],p.cost[1]+1);
		d+=min(p.cost[0]+1,p.cost[1]);
	}
	if(sta[x]==1)	d=inf;
	if(sta[x]==2)	c=inf;
	return {c,inf,inf,d};
}
void update(int x){
	if(!x)	return;
	udt_tree(1,1,n,cnt[x],get_v(x));
	update(pa[lst[num[x]].back()]);
	return;
}
int get_min(){
	node p=get_cost(1,1,n,cnt[1],cnt[lst[num[1]][0]]);
	return min({p.cost[0],p.cost[1],p.cost[2],p.cost[3]});
}
int cat(int v){
	sta[v]=1;
	update(v);
	return get_min();
}
int dog(int v){
	sta[v]=2;
	update(v);
	return get_min();
}
int neighbor(int v){
	sta[v]=0;
	update(v);
	return get_min();
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	11 ms	9728 KB	Output is correct
5	Correct	12 ms	9728 KB	Output is correct
6	Correct	12 ms	9728 KB	Output is correct
7	Correct	13 ms	9728 KB	Output is correct
8	Correct	14 ms	9728 KB	Output is correct
9	Correct	11 ms	9728 KB	Output is correct
10	Correct	13 ms	9728 KB	Output is correct
11	Correct	13 ms	9728 KB	Output is correct
12	Correct	12 ms	9856 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	12 ms	9728 KB	Output is correct
15	Correct	11 ms	9728 KB	Output is correct
16	Correct	11 ms	9728 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	11 ms	9728 KB	Output is correct
5	Correct	12 ms	9728 KB	Output is correct
6	Correct	12 ms	9728 KB	Output is correct
7	Correct	13 ms	9728 KB	Output is correct
8	Correct	14 ms	9728 KB	Output is correct
9	Correct	11 ms	9728 KB	Output is correct
10	Correct	13 ms	9728 KB	Output is correct
11	Correct	13 ms	9728 KB	Output is correct
12	Correct	12 ms	9856 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	12 ms	9728 KB	Output is correct
15	Correct	11 ms	9728 KB	Output is correct
16	Correct	11 ms	9728 KB	Output is correct
17	Correct	16 ms	9856 KB	Output is correct
18	Correct	22 ms	9856 KB	Output is correct
19	Correct	14 ms	9856 KB	Output is correct
20	Correct	11 ms	9728 KB	Output is correct
21	Correct	14 ms	9848 KB	Output is correct
22	Correct	14 ms	9856 KB	Output is correct
23	Correct	22 ms	9920 KB	Output is correct
24	Correct	17 ms	9856 KB	Output is correct
25	Correct	16 ms	9856 KB	Output is correct
26	Correct	16 ms	9776 KB	Output is correct
27	Correct	12 ms	9856 KB	Output is correct
28	Correct	12 ms	9856 KB	Output is correct
29	Correct	13 ms	9856 KB	Output is correct
30	Correct	80 ms	9728 KB	Output is correct
31	Correct	59 ms	9920 KB	Output is correct
32	Correct	153 ms	9848 KB	Output is correct

Subtask #3
0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	12 ms	9728 KB	Output is correct
4	Correct	11 ms	9728 KB	Output is correct
5	Correct	12 ms	9728 KB	Output is correct
6	Correct	12 ms	9728 KB	Output is correct
7	Correct	13 ms	9728 KB	Output is correct
8	Correct	14 ms	9728 KB	Output is correct
9	Correct	11 ms	9728 KB	Output is correct
10	Correct	13 ms	9728 KB	Output is correct
11	Correct	13 ms	9728 KB	Output is correct
12	Correct	12 ms	9856 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	12 ms	9728 KB	Output is correct
15	Correct	11 ms	9728 KB	Output is correct
16	Correct	11 ms	9728 KB	Output is correct
17	Correct	16 ms	9856 KB	Output is correct
18	Correct	22 ms	9856 KB	Output is correct
19	Correct	14 ms	9856 KB	Output is correct
20	Correct	11 ms	9728 KB	Output is correct
21	Correct	14 ms	9848 KB	Output is correct
22	Correct	14 ms	9856 KB	Output is correct
23	Correct	22 ms	9920 KB	Output is correct
24	Correct	17 ms	9856 KB	Output is correct
25	Correct	16 ms	9856 KB	Output is correct
26	Correct	16 ms	9776 KB	Output is correct
27	Correct	12 ms	9856 KB	Output is correct
28	Correct	12 ms	9856 KB	Output is correct
29	Correct	13 ms	9856 KB	Output is correct
30	Correct	80 ms	9728 KB	Output is correct
31	Correct	59 ms	9920 KB	Output is correct
32	Correct	153 ms	9848 KB	Output is correct
33	Correct	1713 ms	17588 KB	Output is correct
34	Correct	491 ms	18680 KB	Output is correct
35	Correct	1624 ms	15536 KB	Output is correct
36	Correct	2625 ms	23116 KB	Output is correct
37	Correct	39 ms	14328 KB	Output is correct
38	Correct	2805 ms	26780 KB	Output is correct
39	Correct	2961 ms	26700 KB	Output is correct
40	Correct	2785 ms	26724 KB	Output is correct
41	Execution timed out	3012 ms	26608 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-

답안 #97795

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 30.0 / 30.0

Subtask #3 0 / 62.0

Subtask #1
8.0 / 8.0

Subtask #2
30.0 / 30.0

Subtask #3
0 / 62.0