Submission #2374753

---

Source Code Expand

#include <stdint.h>
#include <stdio.h>
#include <deque>
#include <vector>

unsigned readUnsigned() {
    int c;
    do { c = ::getchar_unlocked(); } while (c < '0');
    unsigned result = c - '0';
    while ((c = ::getchar_unlocked()) >= '0') {
        result *= 10;
        result += c - '0';
    }
    return result;
}

void writeUnsignedLn(unsigned x) {
    static const unsigned MAX_DIGITS = 10;
    static const unsigned BUF_SIZE = MAX_DIGITS + 1;
    static char buffer[BUF_SIZE] = {0};
    buffer[BUF_SIZE - 1] = '\n';
    unsigned i = BUF_SIZE - 1;
    do {
        buffer[--i] = x % 10 + '0';
        x /= 10;
    } while (x);
    ::fwrite_unlocked(buffer + i, 1, BUF_SIZE - i, stdout);
}

struct Node {
    unsigned color = 0;
    unsigned colordist = 0;
    std::vector<unsigned> edges;
};

struct Paint {
    unsigned v = 0;
    unsigned color = 0;
    unsigned dist = 0;

    Paint(unsigned v = 0, unsigned color = 0, unsigned dist = 0)
        : v(v), color(color), dist(dist)
    {
    }
};

Node NODE[100 * 1000];

int main() {
    unsigned N = readUnsigned();
    unsigned M = readUnsigned();

    for (unsigned i = 0; i < M; ++i) {
        unsigned x = readUnsigned();
        unsigned y = readUnsigned();
        --x, --y;
        NODE[x].edges.push_back(y);
        NODE[y].edges.push_back(x);
    }
    
    unsigned numPaint = readUnsigned();
    std::deque<Paint> jobs;
    for (unsigned i = 0; i < numPaint; ++i) {
        unsigned v = readUnsigned();
        unsigned dist = readUnsigned();
        unsigned color = readUnsigned();
        jobs.push_front(Paint(v - 1, color, dist + 1));
    }

    while (!jobs.empty()) {
        Paint P = jobs.front();
        jobs.pop_front();
        if (NODE[P.v].colordist >= P.dist) {
            continue;
        }
        if (NODE[P.v].color == 0) {
            NODE[P.v].color = P.color;
        }
        NODE[P.v].colordist = P.dist;
        if (P.dist == 1) {
            continue;
        }
        for (unsigned u : NODE[P.v].edges) {
            if (NODE[u].colordist < P.dist - 1) {
                jobs.push_front(Paint(u, P.color, P.dist - 1));
            }
        }
    }

    for (unsigned i = 0; i < N; ++i) {
        writeUnsignedLn(NODE[i].color);
    }
}

Submission Info

Judge Result