#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
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);
}
int lo(int a,int b){return a<b?a:b;}
int t2[N<<2], lz2[N<<2];
void push2(int v, int l, int r)
{
if (1e9>lz2[v])
{
if (l != r) lz2[2*v+1]=lo(lz2[2*v+1],lz2[v]),lz2[2*v+2]=lo(lz2[2*v+2],lz2[v]),
t2[v] = lo(t2[v],lz2[v]);
lz2[v] = 1e9;
}
}
void upd2(int v, int l, int r, int x, int y, int k)
{
push2(v, l, r);
if (r < x||y<l)return;
if(x<=l&&r<=y){lz2[v]=k;push2(v,l,r);return;}
upd2(2*v+1, l,(l+r)/2,x,y,k),upd2(2*v+2,(l+r)/2+1,r,x,y,k);
t2[v]=lo(t2[2*v+1],t2[2*v+2]);
}
int qry2(int v,int l,int r,int x,int y)
{
push2(v,l,r);
if(r<x||y<l)return 1e9;
if (x<=l&&r<=y)return t2[v];
return lo(qry2(2*v+1,l,(l+r)/2,x,y),qry2(2*v+2, (l+r)/2+1, r, x,y));
}
int n,m,h[N],e[N<<1][2],ne=1,y[N],P[19][N],dd[N],ch[N],ci[N],timer=0,w[N],ee[N],sz[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){
P[0][u]=p;
for(int j=1;j<19;++j)P[j][u]=P[j-1][P[j-1][u]];
sz[u]=1;
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=p&&y[j>>1]){
dd[v]=dd[u]+1;
ee[v]=j>>1;
dfs(v,u);
sz[u]+=sz[v];
}
}
void hld(int u,int hh)
{
int hv=0;
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=P[0][u]&&y[j>>1]) if(sz[v]>sz[hv])hv=v;
ci[u]=timer++;ch[u]=hh;
if(hv)hld(hv,hh);
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])!=P[0][u]&&y[j>>1]&&v-hv) hld(v,v);
}
int qq(int u,int v){
if(dd[u]>dd[v])return qq(v,u);
int dt=dd[v]-dd[u];
for(int j=19;j--;)if(dt&(1<<j))v=P[j][v];
if(u==v)return u;
for(int j=19;j--;)if(P[j][u]^P[j][v])u=P[j][u],v=P[j][v];
return P[0][u];
}
int anc(int u,int d)
{
for(int j=19;j--;)if(dd[P[j][u]]>=d)u=P[j][u];
return u;
}
int need[N],np,ord=1;
int cup(int u,int a)
{
int z=0;
for(;ch[u]!=ch[a];u=P[0][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,int k)
{
for(;ch[u]!=ch[a];u=P[0][ch[u]])
upd(0,0,n,ci[ch[u]],ci[u],0),
upd2(0,0,n,ci[ch[u]],ci[u],k);
upd(0,0,n,ci[a],ci[u],0);
upd2(0,0,n,ci[a],ci[u],k);
}
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;
}
static int use[N];
int main(){
memset(lz,-1,sizeof lz);
memset(lz2,63,sizeof lz2);
memset(t2,63,sizeof t2);
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;
dfs(1,1);hld(1,1);
upd(0,0,n,0,n,1);
upd(0,0,n,ci[1],ci[1],0);
upd2(0,0,n,0,n,1e8);
for(int j=1;j<=m;++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),uk=anc(u,dd[lca]+1),vk=anc(v,dd[lca]+1);
ord+=cup(u,uk)+ cup(v,vk);
sup(u,uk,j); sup(v,vk,j);
use[w[j]=ord++]=1;
}else {
if(qry(0,0,n,ci[v],ci[v])){
use[w[j]=ord++]=1;
assert(dd[u]+1==dd[v]);
upd(0,0,n,ci[v],ci[v],0);
}
}
}
for(int u=2;u<=n;++u){
if(!w[ee[u]])
{
at[ee[u]]=qry2(0,0,n,ci[u],ci[u]);
//if(at[ee[u]]>n)assert(0);b
ww[wo++]=ee[u];
}
}
compar=c2;sort(ww,0,wo);
int ord2=1;
for(int j=0;j<wo;++j){
while(use[ord2])++ord2;
w[ww[j]]=ord2++;
//printf(" : %d %d\n",at[ww[j]],ww[j]);
}
for(int j=1;j<=m;++j){
printf("%d ",w[j]);
}
}
Compilation message
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:141:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | for(int u,v,i=1;i<=m;++i)scanf("%d%d",&u,&v),_l(u,v),_l(v,u);
| ~~~~~^~~~~~~~~~~~~~
riggedroads.cpp:142:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | for(int j,i=1;i<n;++i)scanf("%d",&j),y[j]=1;
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
47448 KB |
Output is correct |
| 2 |
Correct |
6 ms |
47452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
47592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
47448 KB |
Output is correct |
| 2 |
Correct |
6 ms |
47452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
47592 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
47452 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
51660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
62652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
238 ms |
67880 KB |
Output is correct |
| 2 |
Correct |
245 ms |
73400 KB |
Output is correct |
| 3 |
Correct |
61 ms |
55536 KB |
Output is correct |
| 4 |
Correct |
85 ms |
58208 KB |
Output is correct |
| 5 |
Correct |
248 ms |
72192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
65692 KB |
Output is correct |
| 2 |
Incorrect |
109 ms |
58964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
47448 KB |
Output is correct |
| 2 |
Correct |
6 ms |
47452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
47592 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
47452 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
