Cod sursă (job #222874)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int Lmax = 60000 + 2;
const int INF = numeric_limits<int>::max() / 2;
const ULL BASE = 137;

ULL base[Lmax];

class Treap
{
private:

    class NodeTreap
    {
    public:

        char key;
        int priority;
        int nr_nodes;

        NodeTreap *st, *dr;

        ULL codeHash;

        NodeTreap(char k, int p, int n, NodeTreap *l, NodeTreap *r) : key(k), priority(p), nr_nodes(n), st(l), dr(r), codeHash(k) {

            this->codeHash = static_cast<ULL>(this->key);
        }

        void update()
        {
            this->nr_nodes = this->st->nr_nodes + this->dr->nr_nodes + 1;

            ULL code = this->st->codeHash;
            code = code * BASE + static_cast<ULL>(this->key);
            code = code * base[this->dr->nr_nodes] + this->dr->codeHash;
            this->codeHash = code;
        }
    };

    NodeTreap *root;
    NodeTreap *NIL;

    void rotateRight(NodeTreap *&T)
    {
        NodeTreap *aux = T->st;
        T->st = aux->dr;
        aux->dr = T;

        T->update();
        aux->update();

        T = aux;
    }

    void rotateLeft(NodeTreap *&T)
    {
        NodeTreap *aux = T->dr;
        T->dr = aux->st;
        aux->st = T;

        T->update();
        aux->update();

        T = aux;
    }

    void balance(NodeTreap *&T)
    {
        if (T->st->priority > T->priority)
            rotateRight(T);

        if (T->dr->priority > T->priority)
            rotateLeft(T);

        T->update();
    }

    void insert(NodeTreap *&T, int pos, char key, int priority = 1 + rand() % (INF - 2))
    {
        if (T == NIL)
        {
            T = new NodeTreap(key, priority, 1, NIL, NIL);
        }
        else
        {
            if (pos <= T->st->nr_nodes + 1)
                insert(T->st, pos, key, priority);
            else
                insert(T->dr, pos - T->st->nr_nodes - 1, key, priority);

            balance(T);
        }
    }

    void erase(NodeTreap *&T, int pos)
    {
        if (T == NIL) return;

        if (T->st->nr_nodes + 1 == pos)
        {
            if (T->st == NIL && T->dr == NIL)
            {
                delete T;
                T = NIL;
            }
            else
            {
                if (T->st->priority > T->dr->priority)
                {
                    rotateRight(T);
                    erase(T->dr, pos - T->st->nr_nodes - 1);
                }
                else
                {
                    rotateLeft(T);
                    erase(T->st, pos);
                }
            }
        }
        else
        {
            if (pos <= T->st->nr_nodes)
                erase(T->st, pos);
            else
                erase(T->dr, pos - T->st->nr_nodes - 1);
        }

        if (T != NIL)
            T->update();
    }

    char kth_element(NodeTreap *&T, int pos)
    {
        if (T->st->nr_nodes + 1 == pos)
            return T->codeHash;

        if (pos <= T->st->nr_nodes)
            return kth_element(T->st, pos);
        else
            return kth_element(T->dr, pos - T->st->nr_nodes - 1);
    }

    void merge(NodeTreap *&root, NodeTreap *&L, NodeTreap *&R)
    {
        root = new NodeTreap(0, INF, 1, L, R);
        root->update();

        erase(root, root->st->nr_nodes + 1);
    }

    /// [0...pos-1] U [pos...sizeTreap]
    void split(NodeTreap *&root, NodeTreap *&L, NodeTreap *&R, int pos)
    {
        insert(root, pos, 'a', INF);

        L = root->st;
        R = root->dr;

        delete root;
        root = NIL;
    }

    void printTree(NodeTreap *&R)
    {
        if (R == NIL) return;

        printTree(R->st);
        cerr << R->key;
        printTree(R->dr);
    }

public:

    Treap() : NIL()
    {
        srand(time(nullptr));
        NIL = new NodeTreap(0, 0, 0, nullptr, nullptr);
        root = NIL;
    }

    /// hash[x...y]
    ULL getHash(int x, int y)
    {
        ULL code = 0;
        NodeTreap *tmp, *T1, *T2, *T3;

        split(root, tmp, T3, y + 1);
        split(tmp, T1, T2, x);
#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;
}