답안 #61536 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61536	2018-07-26T07:16:36 Z	정원준(#1781)	Min-max tree (BOI18_minmaxtree)	C++11	22 / 100	531 ms	45376 KB

minmaxtree

#include <bits/stdc++.h>
#define L long long
#define inf 1987654321

using namespace std;

L n,q;
L sp[70070][20],lev[70070],sz[70070];
L chk[70070],hv[70070],trnum[70070];
L ansma[70070],ansmi[70070];
L ans[70070];

map<L,L>colorcnt;

vector<L>v[70070];

char str[12];

struct pr{
	L tim,val;
};

struct Seg{
	L sz,dep,tim=0,top;
	vector<L>a,t;
	void init(L dep_,L top_){
		dep=dep_;
		top=top_;
		vector<L>temp(sz*4+3,0);
		a=temp;
		t=temp;
	}
	void reinit(){
		tim=0;
		vector<L>temp(sz*4+3,0);
		a=temp;
		t=temp;
	}
	void doupdate(L s,L e,L val){
		L ss=lev[s];
		L ee=lev[e];
		ss-=dep-1;
		ee-=dep-1;
		ss++;
		//printf("%lld %lld\n",ss,ee);
		tim++;
		update(1,1,sz,ss,ee,val);
	}
	L doget(L loc){
		return get(1,1,sz,lev[loc]-dep+1).val;
	}
	void update(L now,L S,L E,L s,L e,L val){
		//printf("%lld %lld %lld %lld %lld %lld\n",now,S,E,s,e,val);
		if(S>e||E<s) return;
		if(s<=S&&E<=e)
		{
			a[now]=val;
			t[now]=tim;
			return;
		}
		L mid=(S+E)/2;
		update(now*2,S,mid,s,e,val);
		update(now*2+1,mid+1,E,s,e,val);
	}
	pr get(L now,L S,L E,L loc){
		//printf("%lld %lld %lld %lld\n",now,S,E,loc);
		if(S>loc||E<loc) return (pr){0,0};
		if(S==E) return (pr){t[now],a[now]};
		L mid=(S+E)/2;
		pr temp1=get(now*2,S,mid,loc);
		pr temp2=get(now*2+1,mid+1,E,loc);
		pr temp3;
		pr temp4=(pr){t[now],a[now]};
		if(temp1.tim>temp2.tim) temp3=temp1;
		else temp3=temp2;
		if(temp4.tim>temp3.tim) return temp4;
		else return temp3;
	}
	
}tr[70070];

void dfs(L x){
	L i;
	trnum[x]=x;
	sz[x]++;
	for(i=0;i<v[x].size();i++)
	{
		if(!chk[v[x][i]])
		{
			chk[v[x][i]]=1;
			sp[v[x][i]][0]=x;
			lev[v[x][i]]=lev[x]+1;
			dfs(v[x][i]);
			sz[x]+=sz[v[x][i]];
		}
	}
	for(i=0;i<v[x].size();i++)
	{
		if((sz[x]-1)/2<sz[v[x][i]]&&v[x][i]!=sp[x][0])
		{
			hv[v[x][i]]=1;
		}
	}
}

void dfs2(L x){
	L i;
	if(!trnum[x]) trnum[x]=x;
	for(i=0;i<v[x].size();i++)
	{
		if(!chk[v[x][i]])
		{
			chk[v[x][i]]=1;
			if(hv[v[x][i]])
			{
				trnum[v[x][i]]=trnum[x];
			}
			dfs2(v[x][i]);
		}
	}
	tr[trnum[x]].sz++;
	if(!hv[x])
	{
		tr[x].init(lev[x],sp[x][0]);
	}
}

L lca(L x,L y){
	if(lev[x]<lev[y]) swap(x,y);
	L i;
	for(i=0;i<20;i++)
	{
		if((lev[x]-lev[y])&(1<<i))
		{
			x=sp[x][i];
		}
	}
	if(x==y) return x;
	for(i=19;i>=0;i--)
	{
		if(sp[x][i]!=sp[y][i])
		{
			x=sp[x][i];
			y=sp[y][i];
		}
	}
	return sp[x][0];
}

struct query{
	L det,s,e,val;
}qr[70070];

bool operator<(query a,query b){
	return a.val>b.val;
}

void giveval(L s,L e,L val){
	while(s!=e)
	{
		//printf("start last %lld %lld\n",s,e);
		if(lev[tr[trnum[s]].top]>=lev[e])
		{
			//printf("seg range %lld %lld\n",tr[trnum[s]].top,s);
			tr[trnum[s]].doupdate(tr[trnum[s]].top,s,val);
			s=tr[trnum[s]].top;
		}
		else
		{
			//printf("seg range %lld %lld\n",e,s);
			tr[trnum[s]].doupdate(e,s,val);
			break;
		}
	}
}

int main()
{
	scanf("%lld",&n);
	L i,j;
	for(i=1;i<n;i++)
	{
		L s,e;
		scanf("%lld %lld",&s,&e);
		v[s].push_back(e);
		v[e].push_back(s);
	}
	sp[1][0]=1;
	chk[1]=1;
	dfs(1);
	for(i=1;i<20;i++)
	{
		for(j=1;j<=n;j++)
		{
			sp[j][i]=sp[sp[j][i-1]][i-1];
		}
	}
	for(i=1;i<=n;i++)
	{
		chk[i]=0;
	}
	chk[1]=1;
	dfs2(1);
	/*for(i=1;i<=n;i++)
	{
		printf("%lld ",trnum[i]);
	}*/
	scanf("%lld",&q);
	for(i=1;i<=q;i++)
	{
		scanf("%s %lld %lld %lld",str,&qr[i].s,&qr[i].e,&qr[i].val);
		if(str[0]=='M') qr[i].det=1;
		else qr[i].det=2;
	}
	sort(qr+1,qr+q+1);
	for(i=1;i<=q;i++)
	{
		if(qr[i].det==2) continue;
		L lc=lca(qr[i].s,qr[i].e);
		giveval(qr[i].s,lc,qr[i].val);
		giveval(qr[i].e,lc,qr[i].val);
	}
	for(i=2;i<=n;i++)
	{
		ansma[i]=tr[trnum[i]].doget(i);
		colorcnt[ansma[i]]++;
	}
	for(i=1;i<=n;i++)
	{
		tr[i].reinit();
	}
	for(i=q;i>=1;i--)
	{
		if(qr[i].det==1) continue;
		L lc=lca(qr[i].s,qr[i].e);
		giveval(qr[i].s,lc,qr[i].val);
		giveval(qr[i].e,lc,qr[i].val);
	}
	for(i=2;i<=n;i++)
	{
		ansmi[i]=tr[trnum[i]].doget(i);
	}
	for(i=2;i<=n;i++)
	{
		//printf("%lld %lld %lld\n",i,ansmi[i],ansma[i]);
		if(ansmi[i]&&ansma[i])
		{
			if(colorcnt[ansma[i]]>1)
			{
				colorcnt[ansma[i]]--;
				ans[i]=ansmi[i];
			}
			else
			{
				ans[i]=ansma[i];
			}
		}
		else if(ansmi[i])
		{
			ans[i]=ansmi[i];
		}
		else if(ansma[i])
		{
			ans[i]=ansma[i];
		}
	}
	for(i=2;i<=n;i++)
	{
		printf("%lld %lld %lld\n",i,sp[i][0],ans[i]);
	}
}

Compilation message

minmaxtree.cpp: In function 'void dfs(long long int)':
minmaxtree.cpp:86:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
minmaxtree.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs2(long long int)':
minmaxtree.cpp:109:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:179:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
minmaxtree.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&s,&e);
   ~~~~~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:208:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&q);
  ~~~~~^~~~~~~~~~~
minmaxtree.cpp:211:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %lld %lld",str,&qr[i].s,&qr[i].e,&qr[i].val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7544 KB	Output is correct
2	Correct	11 ms	7544 KB	Output is correct
3	Correct	8 ms	7600 KB	Output is correct
4	Incorrect	11 ms	7672 KB	Output isn't correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	520 ms	44684 KB	Output is correct
2	Correct	483 ms	44684 KB	Output is correct
3	Correct	516 ms	44684 KB	Output is correct
4	Correct	531 ms	45376 KB	Output is correct
5	Correct	426 ms	45376 KB	Output is correct
6	Correct	481 ms	45376 KB	Output is correct
7	Correct	417 ms	45376 KB	Output is correct

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	295 ms	45376 KB	Output is correct
2	Correct	358 ms	45376 KB	Output is correct
3	Correct	300 ms	45376 KB	Output is correct
4	Correct	310 ms	45376 KB	Output is correct
5	Correct	312 ms	45376 KB	Output is correct
6	Correct	362 ms	45376 KB	Output is correct
7	Correct	286 ms	45376 KB	Output is correct
8	Incorrect	356 ms	45376 KB	Output isn't correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7544 KB	Output is correct
2	Correct	11 ms	7544 KB	Output is correct
3	Correct	8 ms	7600 KB	Output is correct
4	Incorrect	11 ms	7672 KB	Output isn't correct

답안 #61536

Compilation message

Subtask #1 0 / 7.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 29.0

Subtask #4 0 / 42.0

Subtask #1
0 / 7.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 29.0

Subtask #4
0 / 42.0