Editorial for Bedao Grand Contest 04 - REGRA


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const string filename = "REGRA";

typedef pair<int,int> ii;

struct Query
{
    int u,d,x;
    Query(){}
}Q[100001];

bool operator < (const Query &a, const Query &b)
{
    if (a.x != b.x)
        return a.x > b.x;
    return a.d > b.d;
}

int n,m,q;
vector<int> AdjList[100001];
int f[100001][21];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen( (filename + ".inp").c_str(), "r", stdin);
    freopen( (filename + ".out").c_str(), "w", stdout);

    cin >> n >> m >> q;

    // Xay dung do thi ban dau
    for (int i=1;i<=m;i++)
    {   
        int u,v;
        cin >> u >> v;
        AdjList[u].push_back(v);
        AdjList[v].push_back(u);
    }

    // Sort truy van theo x
    for (int i=1;i<=q;i++)
        cin >> Q[i].u >> Q[i].d >> Q[i].x;
    sort(Q+1,Q+1+q);

    for (int i=1;i<=q;i++)
    {
        queue<ii> c;
        if (!f[Q[i].u][Q[i].d])
        {
            f[Q[i].u][Q[i].d] = Q[i].x;

            // BFS tren do thi moi  
            c.push(ii(Q[i].u,Q[i].d));
            while(!c.empty())
            {
                int u = c.front().first;
                int du = c.front().second;
                c.pop();
                if (!du) continue; // d = 0 thi khong di tiep nua
                for (int j=0;j<AdjList[u].size();j++)
                {
                    int v = AdjList[u][j];
                    if (!f[v][du-1])
                    {
                        f[v][du-1] = Q[i].x;
                        c.push(ii(v,du-1));
                    }
                }
            }
        }
    }

    // In ket qua
    for (int i=1;i<=n;i++)
    {
        int ans = 0;
        for (int j=0;j<=20;j++)
            ans = max(ans,f[i][j]);
        cout << ans << ' ';
    }
}           

Comments

Please read the guidelines before commenting.


There are no comments at the moment.