| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61536 |
2018-07-26T07:16:36 Z |
정원준(#1781) |
Min-max tree (BOI18_minmaxtree) |
C++11 |
|
531 ms |
45376 KB |
#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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
