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.
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