| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61567 |
2018-07-26T07:37:50 Z |
정원준(#1781) |
Min-max tree (BOI18_minmaxtree) |
C++11 |
|
1000 ms |
263168 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];
L mat[70070],matched[70070];
vector<L>colors;
vector<L>colorv[70070];
vector<L>v[70070];
map<L,L>colorback;
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;
}
L dfsmat(L x){
//printf("%lld %lld\n",x,colorv[x].size());
L i;
for(i=0;i<colorv[x].size();i++)
{
if(!matched[colorv[x][i]])
{
matched[colorv[x][i]]=1;
mat[colorv[x][i]]=x+1;
return 1;
}
else
{
if(!chk[mat[colorv[x][i]]]&&dfsmat(mat[colorv[x][i]]))
{
mat[colorv[x][i]]=x+1;
return 1;
}
}
}
return 0;
}
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);
colors.push_back(qr[i].val);
if(str[0]=='M') qr[i].det=1;
else qr[i].det=2;
}
sort(colors.begin(),colors.end());
for(i=0;i<colors.size();i++)
{
colorback[colors[i]]=i;
}
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);
}
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++)
{
L cl=ansmi[i];
if(cl>0)
{
colorv[colorback[cl]].push_back(i);
}
cl=ansma[i];
if(cl>0)
{
colorv[colorback[cl]].push_back(i);
}
}
for(i=0;i<colors.size();i++)
{
chk[i]=0;
}
for(i=0;i<colors.size();i++)
{
chk[i]=1;
dfsmat(i);
chk[i]=0;
}
/*for(i=2;i<=n;i++)
{
printf("%lld ",mat[i]);
}*/
for(i=2;i<=n;i++)
{
if(mat[i]) ans[i]=colors[mat[i]-1];
else
{
if(ansmi[i]) ans[i]=ansmi[i];
else if(ansma[i]) ans[i]=ansma[i];
else ans[i]=0;
}
printf("%lld %lld %lld\n",i,sp[i][0],ans[i]);
}
}
Compilation message
minmaxtree.cpp: In function 'void dfs(long long int)':
minmaxtree.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
minmaxtree.cpp:101: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:113:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
minmaxtree.cpp: In function 'long long int dfsmat(long long int)':
minmaxtree.cpp:165:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<colorv[x].size();i++)
~^~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:244:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<colors.size();i++)
~^~~~~~~~~~~~~~
minmaxtree.cpp:289:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<colors.size();i++)
~^~~~~~~~~~~~~~
minmaxtree.cpp:293:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<colors.size();i++)
~^~~~~~~~~~~~~~
minmaxtree.cpp:206:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
minmaxtree.cpp:211: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:235:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&q);
~~~~~^~~~~~~~~~~
minmaxtree.cpp:238: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 |
Runtime error |
886 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
558 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1100 ms |
263168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
886 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
