Submission #1151265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151265		altern23	Rigged Roads (NOI19_riggedroads)	C++20	27 / 100	1092 ms	327680 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<pii, ll> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

ostream& operator << (ostream& os, pair<ll, pii> x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}

const ll MOD = 1e9 + 7;
const ll N = 3e5;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; while(a < 0) a += MOD; a %= MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

vector<ll> adj[N + 5], p(N + 5), dep(N + 5);
ll up[N + 5][30];

void dfs(ll idx, ll par){
    if(par != -1){
        p[idx] = par;
        up[idx][0] = par;
    }
    for(auto i : adj[idx]){
        if(i != par){
            dep[i] = dep[idx] + 1;
            dfs(i, idx);
        }
    }
}

struct DSU{
    ll n;
    vector<ll> par;
    DSU(ll _n){
        n = _n;
        par.resize(n + 5);
        for(int i = 1; i <= n; i++) par[i] = i;
    }

    ll find(ll idx){
        if(par[idx] == idx) return par[idx];
        return par[idx] = find(par[idx]);
    }

    bool join(ll a, ll b){
        a = find(a), b = find(b);
        if(a == b) return false;
        if(dep[a] > dep[b]) swap(a, b);
        par[b] = a;
        return true;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, e; cin >> n >> e;
        vector<ll> u(e + 5), v(e + 5), used(e + 5), ans(e + 5);

        map<pii, ll> mp;
        for(int i = 1; i <= e; i++){
            cin >> u[i] >> v[i];
            mp[{u[i], v[i]}] = mp[{v[i], u[i]}] = i;
        }

        for(int i = 2; i <= n; i++){
            ll idx; cin >> idx;
            adj[u[idx]].push_back(v[idx]);
            adj[v[idx]].push_back(u[idx]);
            used[idx] = 1;
        }

        for(int i = 1; i <= n; i++) p[i] = i;
        dfs(1, -1);

        for(ll LOG = 1; LOG < 30; LOG++){
            for(int i = 1; i <= n; i++){
                up[i][LOG] = up[up[i][LOG - 1]][LOG - 1];
            }
        }

        DSU dsu(n);

        auto lca = [&](ll a, ll b){
            if(dep[a] < dep[b]) swap(a, b);
            ll res = dep[a] - dep[b];
            for(ll j = 0; j < 30; j++){
                if(res & (1LL << j)) a = up[a][j];
            }

            if(a == b) return a;

            for(ll j = 30; j >= 0; --j){
                if(up[a][j] != 0 && up[b][j] != 0 && up[a][j] != up[b][j]){
                    a = up[a][j], b = up[b][j];
                }
            }

            return up[a][0];
        };

        ll cnt = 0;
        for(int i = 1; i <= e; i++){
            if(used[i]){
                if(ans[i]) continue;
                ans[i] = ++cnt;
                dsu.join(u[i], v[i]);
            }
            else{
                ll LCA = lca(u[i], v[i]);
                ll U = dsu.find(u[i]), V = dsu.find(v[i]);
                vector<ll> tmp;
                // cout << LCA << "\n";
                while(U != dsu.find(LCA)){
                    ll nxt = p[U];
                    dsu.join(U, nxt);
                    tmp.push_back(mp[{U, nxt}]);
                    U = dsu.find(nxt);
                }

                while(V != dsu.find(LCA)){
                    ll nxt = p[V];
                    dsu.join(V, nxt);
                    tmp.push_back(mp[{V, nxt}]);
                    V = dsu.find(nxt);
                }
                // cout << LCA << " " << u[i] << " " << v[i] << "\n";
                sort(tmp.begin(), tmp.end());
                for(auto &x : tmp){
                    ans[x] = ++cnt;
                }
                ans[i] = ++cnt;
            }
        }

        for(int i = 1; i <= e; i++){
            cout << ans[i] << " \n"[i == e];
        }
    }   
}

/*

*/  

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