제출 #1251565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251565		Geforgs	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	601 ms	121920 KiB

riggedroads

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bit>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

ll dim=21;

ll get(ll x, vector<ll>& parent){
    if(parent[x] == x) return x;
    return parent[x] = get(parent[x], parent);
}

void unite(ll x, ll y, vector<ll>& parent){
    x = get(x, parent);
    y = get(y, parent);
    if(x == y) return;
    parent[x] = y;
}

void DFS(ll id, ll last, ll d, vector<vector<pair<ll, ll>>>& b, vector<vector<ll>>& up, vector<ll>& prev, vector<ll>& depth){
    depth[id] = d;
    up[id][0] = last;
    for(int i=1;i<dim;++i){
        up[id][i] = up[up[id][i-1]][i-1];
    }
    for(auto el: b[id]){
        if(el.first == last){
            prev[id] = el.second;
            continue;
        }
        DFS(el.first, id, d+1, b, up, prev, depth);
    }
}

ll lca(ll x, ll y, vector<vector<ll>>& up, vector<ll>& depth){
    if(depth[x] < depth[y]) swap(x, y);
    for(int i=dim-1;i>=0;--i){
        if(depth[up[x][i]] >= depth[y]){
            x = up[x][i];
        }
    }
    if(x == y) return x;
    for(int i=dim-1;i>=0;--i){
        if(up[x][i] != up[y][i]){
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

void solve(){
    ll n, m, i, x, t=1, v, w;
    cin>>n>>m;
    vector<pair<ll, ll>> a(m);
    vector<vector<pair<ll, ll>>> b(n);
    vector<ll> parent(n);
    vector<ll> depth(n);
    vector<vector<ll>> up(n, vector<ll>(dim));
    vector<ll> prev(n, -1);
    for(i=0;i<m;++i){
        cin>>a[i].first>>a[i].second;
        --a[i].first;
        --a[i].second;
    }
    for(i=1;i<n;++i){
        cin>>x;
        --x;
        b[a[x].first].pb({a[x].second, x});
        b[a[x].second].pb({a[x].first, x});
        parent[i] = i;
    }
    DFS(0, 0, 0,b, up, prev, depth);
    vector<ll> res(m, -1);
    set<ll> add;
    for(i=0;i<m;++i){
        if(res[i] != -1){
            continue;
        }
        x = lca(a[i].first, a[i].second, up, depth);
        v = get(a[i].first, parent);
        w = get(a[i].second, parent);
        while(depth[v] > depth[x]){
            add.insert(prev[v]);
            unite(v, up[v][0], parent);
            v = get(v, parent);
        }
        while(depth[w] > depth[x]){
            add.insert(prev[w]);
            unite(w, up[w][0], parent);
            w = get(w, parent);
        }
        for(auto el: add){
            res[el] = t++;
        }
        add.clear();
        if(res[i] == -1) res[i] = t++;
    }
    for(auto el: res){
        cout<<el<<' ';
    }
    cout<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32