답안 #97792 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97792	2019-02-18T14:00:09 Z	fefe	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3000 ms	24640 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;
	node p=get_v(x);
	udt_tree(1,1,n,cnt[x],p);
	p=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	11 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	12 ms	9700 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	12 ms	9728 KB	Output is correct
6	Correct	11 ms	9728 KB	Output is correct
7	Correct	11 ms	9728 KB	Output is correct
8	Correct	13 ms	9728 KB	Output is correct
9	Correct	13 ms	9728 KB	Output is correct
10	Correct	12 ms	9728 KB	Output is correct
11	Correct	13 ms	9700 KB	Output is correct
12	Correct	11 ms	9728 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	14 ms	9728 KB	Output is correct
15	Correct	10 ms	9728 KB	Output is correct
16	Correct	12 ms	9728 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	12 ms	9700 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	12 ms	9728 KB	Output is correct
6	Correct	11 ms	9728 KB	Output is correct
7	Correct	11 ms	9728 KB	Output is correct
8	Correct	13 ms	9728 KB	Output is correct
9	Correct	13 ms	9728 KB	Output is correct
10	Correct	12 ms	9728 KB	Output is correct
11	Correct	13 ms	9700 KB	Output is correct
12	Correct	11 ms	9728 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	14 ms	9728 KB	Output is correct
15	Correct	10 ms	9728 KB	Output is correct
16	Correct	12 ms	9728 KB	Output is correct
17	Correct	19 ms	9840 KB	Output is correct
18	Correct	20 ms	9856 KB	Output is correct
19	Correct	17 ms	9856 KB	Output is correct
20	Correct	13 ms	9728 KB	Output is correct
21	Correct	16 ms	9728 KB	Output is correct
22	Correct	18 ms	9856 KB	Output is correct
23	Correct	23 ms	9984 KB	Output is correct
24	Correct	20 ms	9908 KB	Output is correct
25	Correct	17 ms	9856 KB	Output is correct
26	Correct	15 ms	9856 KB	Output is correct
27	Correct	13 ms	9832 KB	Output is correct
28	Correct	14 ms	9856 KB	Output is correct
29	Correct	16 ms	9984 KB	Output is correct
30	Correct	178 ms	9948 KB	Output is correct
31	Correct	97 ms	9976 KB	Output is correct
32	Correct	229 ms	9948 KB	Output is correct

Subtask #3
0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9728 KB	Output is correct
2	Correct	11 ms	9728 KB	Output is correct
3	Correct	12 ms	9700 KB	Output is correct
4	Correct	12 ms	9728 KB	Output is correct
5	Correct	12 ms	9728 KB	Output is correct
6	Correct	11 ms	9728 KB	Output is correct
7	Correct	11 ms	9728 KB	Output is correct
8	Correct	13 ms	9728 KB	Output is correct
9	Correct	13 ms	9728 KB	Output is correct
10	Correct	12 ms	9728 KB	Output is correct
11	Correct	13 ms	9700 KB	Output is correct
12	Correct	11 ms	9728 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	14 ms	9728 KB	Output is correct
15	Correct	10 ms	9728 KB	Output is correct
16	Correct	12 ms	9728 KB	Output is correct
17	Correct	19 ms	9840 KB	Output is correct
18	Correct	20 ms	9856 KB	Output is correct
19	Correct	17 ms	9856 KB	Output is correct
20	Correct	13 ms	9728 KB	Output is correct
21	Correct	16 ms	9728 KB	Output is correct
22	Correct	18 ms	9856 KB	Output is correct
23	Correct	23 ms	9984 KB	Output is correct
24	Correct	20 ms	9908 KB	Output is correct
25	Correct	17 ms	9856 KB	Output is correct
26	Correct	15 ms	9856 KB	Output is correct
27	Correct	13 ms	9832 KB	Output is correct
28	Correct	14 ms	9856 KB	Output is correct
29	Correct	16 ms	9984 KB	Output is correct
30	Correct	178 ms	9948 KB	Output is correct
31	Correct	97 ms	9976 KB	Output is correct
32	Correct	229 ms	9948 KB	Output is correct
33	Correct	2825 ms	18712 KB	Output is correct
34	Correct	692 ms	19576 KB	Output is correct
35	Correct	2437 ms	16524 KB	Output is correct
36	Execution timed out	3021 ms	24640 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-

답안 #97792

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