Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define x first
- #define y second
- #define pb push_back
- #define mp make_pair
- #define sqr(a) ((a) * (a))
- #define sz(a) int((a).size())
- #define all(a) (a).begin(), (a).end()
- #define forn(i, n) for (int i = 0; i < int(n); ++i)
- #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
- template<class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
- return out << "(" << a.x << ", " << a.y << ")";
- }
- template<class A> ostream& operator << (ostream& out, const vector<A> &a) {
- out << "[";
- for (auto it = a.begin(); it != a.end(); ++it) {
- if (it != a.begin())
- out << ", ";
- out << *it;
- }
- return out << "]";
- }
- typedef long long li;
- typedef long double ld;
- typedef pair<int, int> pt;
- const int INF = 1e9;
- const li INF64 = 1e18;
- const int MOD = 1e9 + 7;
- const ld PI = acosl(-1.0);
- const ld EPS = 1e-9;
- mt19937 rnd(time(NULL));
- mt19937_64 rnd64(time(NULL));
- const int N = 100 * 1000 + 13;
- const int M = 1000 * 1000 + 13;
- const int LOGN = 19;
- int n, m;
- pair<pt, pt> e[M];
- vector<pt> g[N];
- bool read() {
- if (scanf("%d%d", &n, &m) != 2)
- return false;
- forn(i, n)
- g[i].clear();
- forn(i, m){
- scanf("%d%d%d", &e[i].y.x, &e[i].y.y, &e[i].x.x);
- --e[i].y.x, --e[i].y.y;
- e[i].x.y = i;
- }
- return true;
- }
- int up[N][LOGN];
- int mx[N][LOGN], mn[N][LOGN];
- int rk[N], p[N];
- int getP(int a){
- return (a == p[a] ? a : p[a] = getP(p[a]));
- }
- bool merge(int a, int b){
- a = getP(a);
- b = getP(b);
- if (a == b)
- return false;
- if (rk[b] > rk[a])
- swap(a, b);
- rk[a] += rk[b];
- p[b] = a;
- return true;
- }
- int h[N];
- void dfs(int v, int p = -1){
- for (auto it : g[v]){
- int u = it.x;
- if (u == p) continue;
- up[u][0] = v;
- mx[u][0] = it.y;
- fore(i, 1, LOGN){
- up[u][i] = up[up[u][i - 1]][i - 1];
- mx[u][i] = max(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
- }
- h[u] = h[v] + 1;
- dfs(u, v);
- }
- }
- int lca(int v, int u, int& l){
- int res = -INF;
- if (h[u] > h[v])
- swap(v, u);
- for (int i = LOGN - 1; i >= 0; --i){
- if (h[up[v][i]] >= h[u]){
- res = max(res, mx[v][i]);
- v = up[v][i];
- }
- }
- if (v == u){
- l = v;
- return res;
- }
- for (int i = LOGN - 1; i >= 0; --i){
- if (up[v][i] != up[u][i]){
- res = max(res, mx[v][i]);
- res = max(res, mx[u][i]);
- v = up[v][i];
- u = up[u][i];
- }
- }
- l = up[v][0];
- res = max(res, mx[v][0]);
- res = max(res, mx[u][0]);
- return res;
- }
- void upd(int v, int u, int val){
- if (v == u) return;
- for (int i = LOGN - 1; i >= 0; --i){
- if (h[up[v][i]] >= h[u]){
- mn[v][i] = min(mn[v][i], val);
- v = up[v][i];
- if (v == u) break;
- }
- }
- }
- int ans[M];
- void solve() {
- memset(ans, -1, sizeof(ans));
- sort(e, e + m);
- forn(i, n) rk[i] = 1, p[i] = i;
- vector<int> mst, notmst;
- forn(i, m){
- if (merge(e[i].y.x, e[i].y.y)){
- mst.pb(i);
- g[e[i].y.x].pb(mp(e[i].y.y, e[i].x.x));
- g[e[i].y.y].pb(mp(e[i].y.x, e[i].x.x));
- }
- else{
- notmst.pb(i);
- }
- }
- forn(i, n) forn(j, LOGN)
- mx[i][j] = -INF;
- dfs(0);
- forn(i, n) forn(j, LOGN)
- mn[i][j] = INF;
- for (auto it : notmst){
- int v = e[it].y.x;
- int u = e[it].y.y;
- int l;
- int res = lca(v, u, l);
- ans[e[it].x.y] = res;
- upd(v, l, e[it].x.x);
- upd(u, l, e[it].x.x);
- }
- for (int j = LOGN - 1; j > 0; --j){
- forn(i, n){
- mn[i][j - 1] = min(mn[i][j - 1], mn[i][j]);
- mn[up[i][j - 1]][j - 1] = min(mn[up[i][j - 1]][j - 1], mn[i][j]);
- }
- }
- for (auto it : mst){
- int v = e[it].y.x;
- int u = e[it].y.y;
- if (h[v] < h[u]) swap(v, u);
- ans[e[it].x.y] = mn[v][0];
- }
- forn(i, m)
- printf("%d\n", ans[i]);
- }
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int tt = clock();
- #endif
- cout << fixed << setprecision(10);
- cerr << fixed << setprecision(10);
- #ifdef _DEBUG
- while (read()) {
- #else
- if (read()) {
- #endif
- solve();
- #ifdef _DEBUG
- cerr << "TIME = " << clock() - tt << endl;
- tt = clock();
- #endif
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement