Submission #1127229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127229		pemguimn	Rigged Roads (NOI19_riggedroads)	C++17	58 / 100	2097 ms	78804 KiB

riggedroads

// https://oj.uz/problem/view/NOI19_riggedroads

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;

const int N = 3e5 + 5, LOG = 20;
int n, m, r[N]; bool mark[N]; pii edges[N];

struct DSU{
    vector<int> par, sz; int n;

    void init(int _n){
        n = _n;
        par.resize(n + 1), sz.resize(n + 1);
        for(int i = 0; i <= n; i++) sz[i] = 1, par[i] = i;
    }

    void reset(){
        for(int i = 0; i <= n; i++) sz[i] = 1, par[i] = i;
    }

    int root(int x){
        return (x == par[x] ? x : root(par[x]));
    }

    void unite(int x, int y){
         x = root(x), y = root(y);
         if(x != y){
            sz[x] += sz[y], par[y] = x;
         }
    }
};
bool c1(){
    return max(n, m) <= 9;
}
namespace sub1{
    struct edge{
        int w, x, y, id;
    };
    void solve(){
        vector<int> p(m); iota(p.begin(), p.end(), 1);
        DSU cur; cur.init(n);
        do{
            cur.reset();
            vector<edge> wedge;
            for(int i = 1; i <= m; i++){
                wedge.push_back({p[i - 1], edges[i].first, edges[i].second, i});
            }
            sort(wedge.begin(), wedge.end(), [](edge x, edge y){return x.w < y.w;});
            bool flag = true;
            for(edge x : wedge){
                if(cur.root(x.x) != cur.root(x.y)){
                    cur.unite(x.x, x.y);
                    if(!mark[x.id]) flag = false;
                }
            }
            if(flag){
                for(int &x : p) cout << x << ' '; return;
            }
        } while(next_permutation(p.begin(), p.end()));
    }
}

namespace full{
    int ans[N], t[N], h[N], sz[N], tin[N], tout[N], st[N], par[LOG][N], timedfs = 0;
    vector<pii> adj[N];
    set<int> s[N];
    int seg[4 * N], lazy[4 * N], mn[N];

    void apply(int id, int tl, int tr, int x){
        seg[id] = x * (tr - tl + 1);
        lazy[id] = x;
    }

    void down(int id, int tl, int tr){
        int &t = lazy[id], mid = (tl + tr) / 2;
        if(t ==- 1) return;
        apply(id * 2, tl, mid, t), apply(id * 2 + 1, mid + 1, tr, t);
        t = -1;
    }

    void upd(int id, int tl, int tr, int l, int r, int x){
        if(r < tl || tr < l) return;
        if(l <= tl && tr <= r){apply(id, tl, tr, x); return;}
        int mid = (tl + tr) / 2; down(id, tl, tr);
        upd(id * 2, tl, mid, l, r, x), upd(id * 2 + 1, mid + 1, tr, l, r, x);
        seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }

    int query(int id, int tl, int tr, int l, int r){
        if(r < tl || tr < l) return 0;
        if(l <= tl && tr <= r) return seg[id];
        int mid = (tl + tr) / 2; down(id, tl, tr);
        return query(id * 2, tl, mid, l, r) + query(id * 2 + 1, mid + 1, tr, l, r);
    }

    void dfs(int i, int pre){
        sz[i] = 1;
        for(pii e : adj[i]){
            int x = e.first;
            if(x == pre) continue;
            h[x] = h[i] + 1, par[0][x] = i;
            for(int j = 1; j < LOG; j++) par[j][x] = par[j - 1][par[j - 1][x]];
            dfs(x, i);
            sz[i] += sz[x];
        }
    }

    int lca(int x, int y){
        if(h[x] < h[y]) swap(x, y);
        int d = h[x] - h[y];
        for(int i = 0; i < LOG; i++) if(d & (1 << i)) x = par[i][x];
        if(x == y) return x;
        for(int i = LOG - 1; i >= 0; i--)
            if(par[i][x] != par[i][y]) x = par[i][x], y = par[i][y];
        return par[0][x];
    }

    void dfs1(int i, int pre, int head){
        tin[i] = ++timedfs, st[i] = head;
        upd(1, 1, n, tin[i], tin[i], 1);
        int child = 0;
        for(pii e : adj[i]){
            int x = e.first;
            if(x == pre) continue;
            if(sz[child] < sz[x]) child = x;
        }

        if(child) dfs1(child, i, head);
        for(pii e : adj[i]){
            int x = e.first;
            if(x == pre || x == child) continue;
            dfs1(x, i, x);
        }
        tout[i] = timedfs;
    }

    int qnu(int x, int y){
        int u = lca(x, y), ans = 0;
        if(h[x] < h[y]) swap(x, y);
        while(x != u || y != u){
            if(st[x] == st[u]){
                ans += query(1, 1, n, tin[u] + 1, tin[x]); upd(1, 1, n, tin[u] + 1, tin[x], 0);
                x = u;
                swap(x, y);
            } else{
                ans += query(1, 1, n, tin[st[x]], tin[x]); upd(1, 1, n, tin[st[x]], tin[x], 0);
                x = par[0][st[x]];
            }
        }
        return ans;
    }

    void dfs2(int i, int pre, int lead){
        for(pii e : adj[i]){
            int x = e.first, id = e.second;
            if(x == pre) continue;
            dfs2(x, i, id);
            if(s[i].size() < s[x].size()) swap(s[i], s[x]);
            for(int y : s[x]){
                if(s[i].find(y) == s[i].end()) s[i].insert(y);
                else s[i].erase(y);
            }
        }
        if(!s[i].empty()) mn[lead] = *s[i].begin();
    }
    void solve(){
        memset(lazy, -1, sizeof lazy);
        for(int i = 1; i < n; i++){
            adj[edges[r[i]].first].push_back({edges[r[i]].second, r[i]});
            adj[edges[r[i]].second].push_back({edges[r[i]].first, r[i]});
        }
        dfs(1, 1); dfs1(1, 1, 1);
        int curmx = 0; set<int> weight;
        for(int i = 1; i <= m; i++) weight.insert(i), mn[i] = m + 1;
        for(int i = 1; i <= m; i++){
            int turned = qnu(edges[i].first, edges[i].second);
            if(turned == 0 && mark[i]) continue;
            curmx += 1 + (mark[i] ? 0 : turned);
            s[edges[i].first].insert(curmx);
            s[edges[i].second].insert(curmx);
            weight.erase(curmx);
            ans[i] = curmx;
        }
        dfs2(1, 1, 0);
        for(int i = m; i >= 1; i--){
            if(ans[i] == 0){
                auto it = weight.upper_bound(mn[i]);
                it = prev(it);
                ans[i] = *it;
                weight.erase(*it);
            }
        }
        for(int i = 1; i <= m; i++) cout << ans[i] << ' ';
    }
}

namespace sol2{
    int ans[N], h[N], par[N], lead[N];
    vector<pii> adj[N];
    DSU a;

    void dfs(int i, int pre){
        for(pii e : adj[i]){
            int x = e.first, eid = e.second;
            if(x == pre) continue;
            h[x] = h[i] + 1, par[x] = i, lead[x] = eid;
            dfs(x, i);
        }
    }
    void solve(){
        for(int i = 1; i < n; i++){
            adj[edges[r[i]].first].push_back({edges[r[i]].second, r[i]});
            adj[edges[r[i]].second].push_back({edges[r[i]].first, r[i]});
        }
        dfs(1, 1);
        vector<int> v;
        a.init(n); int mex = 0;
        for(int i = 1; i <= m; i++){
            if(h[edges[i].first] < h[edges[i].second]) swap(edges[i].first, edges[i].second);
            int x = edges[i].first, y = edges[i].second;
            if(mark[i]){
                if(ans[lead[x]] == 0){
                    a.unite(par[x], x);
                    ans[i] = ++mex;
                }
            } else{
                x = a.root(x), y = a.root(y);
                v.clear();
                while(x != y){
                    if(h[x] < h[y]) swap(x, y);
                    v.push_back(lead[x]);
                    a.unite(par[x], x);
                    x = a.root(x);
                }
                sort(v.begin(), v.end());
                for(int x : v) ans[x] = ++mex;
                ans[i] = ++mex;
            }
        }
        for(int i = 1; i <= m; i++) cout << ans[i] << ' ';
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "PALACE"
//    if(fopen(task ".inp", "r")){
//        freopen(task ".inp", "r", stdin);
//        freopen(task ".out", "w", stdout);
//    }

    // Input Output

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        edges[i] = {x, y};
    }

    for(int i = 1; i < n; i++){
        cin >> r[i];
        mark[r[i]] = true;
    }

    // Subtask

    {
//        if(c1()) return sub1::solve(), 0;
        sol2::solve();
    }
    return 0;
}

/*
4 5
3 4
1 2
2 3
1 3
1 4
2 4 5

4 4
1 2
1 4
2 3
3 4
1 3 4
*/

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