Cod sursă (job #204153)

#include <stdio.h>
#include <ctype.h>
#define BUF_SIZE 4096
#define MAXN 500000
#define MAXM 600000
int e, v[MAXN+1], val[2*MAXM+1], next[2*MAXM+1], lista[MAXN+1], q[2][MAXN], st[2], dr[2], r[2][MAXN], poz[MAXN+1], cost[MAXN+1], ok[MAXN+1], pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char getch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=getch();
    while(!isdigit(ch)){
        ch=getch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=getch();
    }
    return x;
}
inline void adauga(int x, int y){
    e++;
    val[e]=y;
    next[e]=lista[x];
    lista[x]=e;
}
int main(){
    int n, m, k, x, y, i, t, p;
    FILE *fout;
    fin=fopen("evacuare.in", "r");
    fout=fopen("evacuare.out", "w");
    n=read();
    m=read();
    k=read();
    for(i=0; i<m; i++){
        x=read();
        y=read();
        adauga(x, y);
        adauga(y, x);
    }
    for(i=1; i<=n; i++){
        v[i]=read();
    }
    q[0][0]=k;
    st[0]=0;
    dr[0]=1;
    cost[k]=0;
    poz[k]=0;
    r[0][0]=1;
    ok[k]=1;
    st[1]=dr[1]=0;
    t=0;
    while(st[t]<dr[t]){
        x=q[t][st[t]];
        p=lista[x];
        while(p){
            if(v[x]==val[p]){
                if(ok[val[p]]==0){
                    ok[val[p]]=1;
                    cost[val[p]]=cost[x];
                    q[t][dr[t]++]=val[p];
                    r[t][dr[t]-1]=1;
                }else if(cost[val[p]]>cost[x]){
                    cost[val[p]]=cost[x];
                    r[(t+1)&1][poz[val[p]]]=0;
                    q[t][dr[t]++]=val[p];
                    r[t][dr[t]-1]=1;
                }
            }else if(ok[val[p]]==0){
                ok[val[p]]=1;
                cost[val[p]]=cost[x]+1;
                poz[val[p]]=dr[(t+1)&1];
                r[(t+1)&1][poz[val[p]]]=1;
                q[(t+1)&1][dr[(t+1)&1]++]=val[p];
            }
            p=next[p];
        }
        st[t]++;
        while((st[t]<dr[t])&&(r[t][st[t]]==0)){
            st[t]++;
        }
        if(st[t]==dr[t]){
            t=(t+1)&1;
            while((st[t]<dr[t])&&(r[t][st[t]]==0)){
                st[t]++;
            }
        }
    }
    for(i=1; i<=n; i++){
        fprintf(fout, "%d\n", cost[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
#include <stdio.h>
#include <ctype.h>
#define BUF_SIZE 4096
#define MAXN 500000
#define MAXM 600000
int e, v[MAXN+1], val[2*MAXM+1], next[2*MAXM+1], lista[MAXN+1], q[2][MAXN], st[2], dr[2], r[2][MAXN], poz[MAXN+1], cost[MAXN+1], ok[MAXN+1], pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char getch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=getch();
    while(!isdigit(ch)){
        ch=getch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=getch();
    }
    return x;
}
inline void adauga(int x, int y){
    e++;
    val[e]=y;
    next[e]=lista[x];
    lista[x]=e;
}
int main(){
    int n, m, k, x, y, i, t, p;
    FILE *fout;
    fin=fopen("evacuare.in", "r");
    fout=fopen("evacuare.out", "w");
    n=read();
    m=read();
    k=read();
    for(i=0; i<m; i++){
        x=read();
        y=read();
        adauga(x, y);
        adauga(y, x);
    }
    for(i=1; i<=n; i++){
        v[i]=read();
    }
    q[0][0]=k;
    st[0]=0;
    dr[0]=1;
    cost[k]=0;
    poz[k]=0;
    r[0][0]=1;
    ok[k]=1;
    st[1]=dr[1]=0;
    t=0;
    while(st[t]<dr[t]){
        x=q[t][st[t]];
        p=lista[x];
        while(p){
            if(v[x]==val[p]){
                if(ok[val[p]]==0){
                    ok[val[p]]=1;
                    cost[val[p]]=cost[x];
                    q[t][dr[t]++]=val[p];
                    r[t][dr[t]-1]=1;
                }else if(cost[val[p]]>cost[x]){
                    cost[val[p]]=cost[x];
                    r[(t+1)&1][poz[val[p]]]=0;
                    q[t][dr[t]++]=val[p];
                    r[t][dr[t]-1]=1;
                }
            }else if(ok[val[p]]==0){
                ok[val[p]]=1;
                cost[val[p]]=cost[x]+1;
                poz[val[p]]=dr[(t+1)&1];
                r[(t+1)&1][poz[val[p]]]=1;
                q[(t+1)&1][dr[(t+1)&1]++]=val[p];
            }
            p=next[p];
        }
        st[t]++;
        while((st[t]<dr[t])&&(r[t][st[t]]==0)){
            st[t]++;
        }
        if(st[t]==dr[t]){
            t=(t+1)&1;
            while((st[t]<dr[t])&&(r[t][st[t]]==0)){
                st[t]++;
            }
        }
    }
    for(i=1; i<=n; i++){
        fprintf(fout, "%d\n", cost[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}