#include<stdio.h>
#include<assert.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 t0[N<<1];
void u_(int l,int r,int k){
for(l+=N,r+=N+1;l<r;l>>=1,r>>=1){
if(l&1)t0[l]=hi(t0[l],k),++l;
if(r&1)--r,t0[r]=hi(t0[r],k);
}
}
int q_(int p){
int z=0;
for(p+=N;p>>=1;)z=hi(z,hi(t0[p<<1],t0[p<<1|1]));
return z;
}
int ttt[N],set[N],n,m,h[N],e[N][3],ne,y[N],id,pp[N],jj[N],ee[N],dd[N],w[N],tin[N],tout[N],timer;
void _l(int u,int v){e[++ne][0]=v,e[ne][2]=h[u],h[u]=ne;}
void __u(int*t,int p,int k){ for(;p<N;p+=p&-p)t[p]+=k; }
int __q(int*t,int p){int z=0;for(;p;p-=p&-p)z+=t[p];return z;}
int __s(int*t,int k){int p=0,v=0,j=1<<20;for(;j>>=1;)if(p+j<N&&v+t[p+j]<k)v+=t[p+=j];return p+1;}
void doedge(int v,int k){
__u(ttt,tin[v],k);
__u(ttt,tout[v]+1,-k);
}
void dfs(int u,int p){
tin[u]=timer++;
for(int v,j=h[u];j;j=e[j][2])if((v=e[j][0])-p){
if(!y[(j+1)/2])continue;
dd[v]=dd[pp[v]=u]+1;
ee[v]=(j+1)/2;
pp[v]=u;
jj[v]=(dd[p]-dd[jj[u]]==dd[jj[u]]-dd[jj[jj[u]]])?jj[jj[u]]:u;
dfs(v,u);
doedge(v,1);
}
tout[u]=timer-1;
}
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];
if(jj[v]-jj[u])u=jj[u],v=jj[v];
else u=pp[u],v=pp[v];
return u;
}
int nx(int u,int aa){
int base=__q(ttt,tin[u]);
while(dd[u]>dd[aa]&&__q(ttt,tin[pp[u]])==base){
u=(__q(ttt,tin[jj[u]])==base)?jj[u]:pp[u];
}
return u;
}
int need[N],np,ord[N],no;
int c1(int i,int j){return ee[i]<ee[j]?-1:ee[i]>ee[j]?1:0;}
int main(){
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),__u(set,i,1);
for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
pp[1]=jj[1]=1;dfs(1,1);
int ord = 1;
for(int j=1;j<=m;++j){
int u=e[j*2-1][0],v=e[j*2][0],lca;
if(w[j])continue;
if(!y[j]){
int lca=qq(u,v);
int left=__q(ttt,tin[u])+__q(ttt,tin[v]);
//int low=q_(tin[lca])+1;
//int at=low;
//for(int jj=1;jj<=left;++jj,++at)ord[no++]=__s(set,at);
//printf("LEFT: %d (%d %d) (%d)\n",left,low,at,__q(ttt,tin[u]));
//w[j]=__s(set,at);
for(int ii=nx(u,lca);dd[ii]>dd[lca];ii=nx(ii,lca)) doedge(ii,-1),need[np++]=ii;
for(int ii=nx(v,lca);dd[ii]>dd[lca];ii=nx(ii,lca)) doedge(ii,-1),need[np++]=ii;
compar=c1;sort(need,0,np);
//printf("NP : %d\n",np);
for(int i=0;i<np;++i){
//printf(" %d DONE %d\n",ee[need[i]],ord);
//w[ee[need[i]]]=ord[i];
w[ee[need[i]]]=ord;
__u(set,ord,-1);
u_(tin[need[i]],tout[need[i]],ord++);
}
np=no=0;
__u(set,w[j]=ord++,-1);
//printf(" %d DONE\n",j);
}else{
if(dd[v]+1==dd[u]){int t=u;u=v;v=t;}
assert(dd[u]+1==dd[v]);
w[j]=ord++;
doedge(v,-1);
u_(tin[v],tout[v],w[j]);
__u(set,w[j],-1);
}
}
for(int j=1;j<=m;++j)printf("%d ",w[j]);
}
Compilation message
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:81:17: warning: unused variable 'left' [-Wunused-variable]
81 | int left=__q(ttt,tin[u])+__q(ttt,tin[v]);
| ^~~~
riggedroads.cpp:77:39: warning: unused variable 'lca' [-Wunused-variable]
77 | int u=e[j*2-1][0],v=e[j*2][0],lca;
| ^~~
riggedroads.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:71:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u),__u(set,i,1);
| ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:72:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
15184 KB |
Output is correct |
| 2 |
Runtime error |
213 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
276 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
29012 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
255 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
