Submission #1126992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126992		Icelast	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	602 ms	127832 KiB

riggedroads

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct edge{
    int u, v;
};
struct DSU{
    int n;
    vector<int> pa, sz;
    vector<vector<int>> node;
    DSU(int n) : n(n){
        pa.resize(n+1);
        sz.resize(n+1, 1);
        node.resize(n+1);
        for(int i = 0; i <= n; i++){
            pa[i] = i;
            node[i].push_back(i);
        }
    };
    int find(int x){
        while(x != pa[x]){
            x = pa[x] = pa[pa[x]];
        }
        return x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        pa[y] = x;
        sz[x] += sz[y];
        return true;
    }
    int size(int x){
        return sz[find(x)];
    }
};
struct Tree{
    int n, root;
    vector<int> depth, head, sz, pa;
    vector<int> f;
    Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
        depth.resize(n+1, -1);
        head.resize(n+1);
        sz.resize(n+1, 0);
        pa.resize(n+1, -1);
        auto rootTree = [&](auto rootTree, int u, int p) -> void{
            depth[u] = depth[p]+1;
            pa[u] = p;
            sz[u] = 1;
            for(int v : adj[u]){
                if(v == p) continue;
                rootTree(rootTree, v, u);
                sz[u] += sz[v];
            }
        };
        rootTree(rootTree, root, 0);
        auto decompose = [&](auto decompose, int u, int h) -> void{
            head[u] = h;
            int heavy = -1;
            for(int v : adj[u]){
                if(v == pa[u]) continue;
                if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
            }
            if(heavy != -1) decompose(decompose, heavy, h);
            for(int v : adj[u]){
                if(v == pa[u] || v == heavy) continue;
                decompose(decompose, v, v);
            }
        };
        decompose(decompose, root, root);
        f = [&]{
            vector<array<int, 2>> first(n+1);
            vector<array<int, 2>> second(n+1);
            function<void(int, int)> dfs0 = [&](int u, int p) {
                first[u] = second[u] = {0, -1};
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    dfs0(v, u);
                    auto fetch = first[v];
                    fetch[0] += 1;
                    fetch[1] = v;
                    if (fetch > first[u]) {
                        swap(fetch, first[u]);
                    }
                    if (fetch > second[u]) {
                        swap(fetch, second[u]);
                    }
                }
            };
            dfs0(1, 0);

            function<void(int, int)> dfs = [&](int u, int p) {
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    auto fetch = first[u][1] == v ? second[u] : first[u];
                    fetch[0] += 1;
                    fetch[1] = u;
                    if (fetch > first[v]) {
                        swap(fetch, first[v]);
                    }
                    if (fetch > second[v]) {
                        swap(fetch, second[v]);
                    }
                    dfs(v, u);
                }
            };
            dfs(1, 0);
            vector<int> f(n+1);
            for (int u = 1; u <= n; u++) {
                f[u] = first[u][0];
            }
            return f;
        }();
    };
    int lca(int u, int v){
        for(; head[u] != head[v]; v = pa[head[v]]){
            if(depth[head[u]] > depth[head[v]]) swap(u, v);
        }
        if(depth[u] > depth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u, v)];
    }
};
void sub2(int n, int m, vector<vector<pair<int, int>>> adj, vector<edge> e, vector<int> ed){
    vector<int> ans(m+1, 0);
    vector<vector<int>> tree(n+1);
    vector<vector<pair<int, int>>> tree2(n+1);
    for(int i = 1; i <= m; i++){
        if(ed[i]){
            tree[e[i].u].push_back(e[i].v);
            tree[e[i].v].push_back(e[i].u);
            tree2[e[i].u].push_back({e[i].v, i});
            tree2[e[i].v].push_back({e[i].u, i});
        }
    }
    Tree Y(n, 1, tree);
    vector<pair<int, int>> pa(n+1);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        for(auto it : tree2[u]){
            int v = it.first, id = it.second;
            if(v == p) continue;
            pa[v] = {u, id};
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);
    int c = 0;
    for(int i = 1; i <= m; i++){
        if(ans[i] != 0) continue;
        int u = e[i].u, v = e[i].v;
        c++;
        if(ed[i]){
            ans[i] = c;
        }else{
            vector<int> a;
            int lca = Y.lca(u, v);
            int s = u;
            while(s != lca){
                a.push_back(pa[s].second);
                s = pa[s].first;
            }
            s = v;
            while(s != lca){
                a.push_back(pa[s].second);
                s = pa[s].first;
            }
            sort(a.begin(), a.end());
            for(int i : a){
                if(ans[i] != 0) continue;
                ans[i] = c;
                c++;
            }
            ans[i] = c;
        }
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i] << " ";
    }
}
void subfull(int n, int m, vector<vector<pair<int, int>>> adj, vector<edge> e, vector<int> ed){
    vector<int> ans(m+1, 0);
    vector<vector<int>> tree(n+1);
    vector<vector<pair<int, int>>> tree2(n+1);
    for(int i = 1; i <= m; i++){
        if(ed[i]){
            tree[e[i].u].push_back(e[i].v);
            tree[e[i].v].push_back(e[i].u);
            tree2[e[i].u].push_back({e[i].v, i});
            tree2[e[i].v].push_back({e[i].u, i});
        }
    }
    Tree Y(n, 1, tree);
    vector<pair<int, int>> pa(n+1);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        for(auto it : tree2[u]){
            int v = it.first, id = it.second;
            if(v == p) continue;
            pa[v] = {u, id};
            dfs(dfs, v, u);
        }
    };
    DSU dsu(n+1);
    dfs(dfs, 1, 0);
    int c = 0;
    for(int i = 1; i <= m; i++){
        if(ans[i] != 0) continue;
        int u = e[i].u, v = e[i].v;
        c++;
        if(ed[i]){
            ans[i] = c;
        }else{
            vector<int> a;
            int lca = Y.lca(u, v);
            int s = u;
            s = dsu.find(s);
            while(Y.depth[s] > Y.depth[lca]){
                a.push_back(pa[s].second);
                dsu.merge(pa[s].first, s);
                s = dsu.find(s);
            }
            s = v;
            s = dsu.find(s);
            while(Y.depth[s] > Y.depth[lca]){
                a.push_back(pa[s].second);
                dsu.merge(pa[s].first, s);
                s = dsu.find(s);
            }
            sort(a.begin(), a.end());
            for(int i : a){
                if(ans[i] != 0) continue;
                ans[i] = c;
                c++;
            }
            ans[i] = c;
        }
    }
    for(int i = 1; i <= m; i++){
        cout << ans[i] << " ";
    }
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n+1);
    vector<edge> e(m+1);
    vector<int> ed(m+1, 0);
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for(int i = 1; i <= n-1; i++){
        int id;
        cin >> id;
        ed[id] = 1;
    }
    if(n <= 1000 && m <= 1000){
        sub2(n, m, adj, e, ed);
        return;
    }
    subfull(n, m, adj, e, ed);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("PALACE.inp", "r", stdin);
    //freopen("PALACE.out", "w", stdout);
    solve();
}

• 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