This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
#include<string.h>
int hi(int a,int b){return a>b?a:b;}
unsigned X=12345;int rand_(){return(X*=3)>>1;}
int(*compar)(int,int);void sort(int*aa,int l,int r){ while(l<r){ int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)]; while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;break;case 1:t=aa[--k],aa[k]=aa[j],aa[j]=t;break;}sort(aa,l,i);l=k; }}
#define N 300005
int t[N<<2], lz[N<<2];
void push(int v, int l, int r)
{
if (~lz[v])
{
if (l != r) lz[2*v+1] = lz[2*v+2] = lz[v];
t[v] = lz[v]*(r-l+1);
lz[v] = -1;
}
}
void upd(int v, int l, int r, int x, int y, int k)
{
push(v, l, r);
if (r < x||y<l)return;
if(x<=l&&r<=y){lz[v]=k;push(v,l,r);return;}
upd(2*v+1, l,(l+r)/2,x,y,k),upd(2*v+2,(l+r)/2+1,r,x,y,k);
t[v]=t[2*v+1]+t[2*v+2];
}
int qry(int v,int l,int r,int x,int y)
{
push(v,l,r);
if(r<x||y<l)return 0;
if (x<=l&&r<=y)return t[v];
return qry(2*v+1,l,(l+r)/2,x,y)+qry(2*v+2, (l+r)/2+1, r, x,y);
}
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
int n,m,h[N],e[N<<1][2],ne=1,y[N],id,pp[N],jj[N],dd[N],ch[N],ci[N],timer=0,w[N],ee[N],eee[N],sz[N],hv[N];
void _l(int u,int v){e[++ne][0]=v,e[ne][1]=h[u],h[u]=ne;}
void dfs(int u,int p){
sz[u]=1;
hv[u]=0;
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=p&&y[j>>1]){
dd[v]=dd[pp[v]=u]+1;
ee[v]=j>>1;
eee[j>>1]=v;
pp[v]=u;
jj[v]=(dd[p]-dd[jj[u]]==dd[jj[u]]-dd[jj[jj[u]]])?jj[jj[u]]:u;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[hv[u]])hv[u]=v;
}
}
void hld(int u,int hh)
{
ci[u]=timer++;ch[u]=hh;
if(hv[u])hld(hv[u],hh);
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=pp[u]&&y[j>>1]&&v-hv[u]) hld(v,v);
}
int anc(int u,int d){
while(dd[u]>d) u=(dd[jj[u]]>=d)?jj[u]:pp[u];
return u;
}
int qq(int u,int v){
if(dd[u]>dd[v])return qq(v,u);
while(dd[v]>dd[u])
if(dd[jj[v]]>=dd[u]) v=jj[v];
else v=pp[v];
while(u-v)
if(jj[v]-jj[u])u=jj[u],v=jj[v];
else u=pp[u],v=pp[v];
return u;
}
int need[N],np,ord=1;
int c1(int i,int j){return i<j?-1:i>j?1:0;}
int cup(int u,int a)
{
int z=0;
for(;ch[u]!=ch[a];u=pp[ch[u]])
z+=qry(0,0,n,ci[ch[u]],ci[u]);
z+=qry(0,0,n,ci[a],ci[u]);
return z;
}
void sup(int u,int a)
{
for(;ch[u]!=ch[a];u=pp[ch[u]])
upd(0,0,n,ci[ch[u]],ci[u],0);
upd(0,0,n,ci[a],ci[u],0);
}
#include<stdlib.h>
int *eh[N+N],eo[N];
void append(int i,int j){
int o=eo[i]++;
if(o>=2&&(o&(o-1))==0)eh[i]=(int*)realloc(eh[i],o*2*sizeof**eh);
eh[i][o]=j;
}
#include<string>
#include<set>
std::multiset<int>mp;
int ww[N],wo,at[N];
int c2(int i,int j){
if(at[i]-at[j])return at[i]<at[j]?-1:1;
return i<j?-1:i>j?1:0;
}
void dfs2(int u,int p)
{
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=p&&y[j>>1]){
dfs2(v,u);
}
for(int x,j=0;j<eo[u];++j){
x=eh[u][j];
if(x>0) mp.insert(x);
}
for(int x,j=0;j<eo[u];++j){
x=eh[u][j];
if(x<0)mp.erase(x);
}
if(!w[ee[u]]&&ee[u])
{
at[ee[u]]=*mp.begin();
ww[wo++]=ee[u];
}
}
static int use[N];
#include<algorithm>
int main(){
memset(lz,-1,sizeof lz);
for(int i=0;i<N+N;++i)eh[i]=(int*)malloc(2*sizeof**eh);
scanf("%d%d",&n,&m);
for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
pp[1]=jj[1]=1;dfs(1,1);hld(1,1);
upd(0,0,n,0,n,1);
upd(0,0,n,ci[1],ci[1],0);
for(int j=1;j<=m;++j)if(!w[j]){
int u=e[j*2][0],v=e[j*2+1][0];
if(dd[v]+1==dd[u]){int t=u;u=v;v=t;}
if(!y[j]){
int lca=qq(u,v);
int left=cup(u,anc(u,dd[lca]+1))+ cup(v,anc(v,dd[lca]+1));
ord+=left;
sup(u,anc(u,dd[lca]+1)); sup(v,anc(v,dd[lca]+1));
append(u,j);
append(v,j);
append(lca,-j);
w[j]=ord++;
upd(0,0,n,ci[eee[j]],ci[eee[j]],0);
}else {
if(qry(0,0,n,ci[eee[j]],ci[eee[j]])){
w[j]=ord++;
upd(0,0,n,ci[eee[j]],ci[eee[j]],0);
}
}
}
for(int i=1;i<=m;++i)use[w[i]]=1;
dfs2(1,1);
compar=c2;sort(ww,0,wo);
int ord2=1;
for(int j=0;j<wo;++j){
while(use[ord2])++ord2;
w[ww[j]]=ord2++;
}
for(int j=1;j<=m;++j)printf("%d ",w[j]);
}
Compilation message (stderr)
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/basic_string.h:39,
from /usr/include/c++/10/string:55,
from riggedroads.cpp:109:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:147:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
| ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:148:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
| ~~~~~^~~~~~~~~