oj.uz

Submission #1042394

# Submission time Handle Problem Language Result Execution time Memory
1042394 2024-08-03T03:36:44 Z ilovveyyou Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 524 ms 96952 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define popcount __builtin_popcount
#define lg(x) (63 - clz(x))
 
template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        return (x < y ? x = y, true : false);
    }
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        return (x > y ? x = y, true : false);
    }
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a)); a.resize(unique(all(a)) - a.begin());
    }
 
const ll oo = (ll) 1e18, inf = (ll) 1e9, mod = (ll) 1e9 + 7;
const int mxn = (int) 4e5 + 5, S = (int) 450, S2 = (int) 450, lg = (int) 18;
 
void add(ll &x, ll y) {
    x += y;
    if (x >= mod) x -= mod;
}
 
void sub(ll &x, ll y) {
    x -= y;
    if (x < 0) x += mod;
}
 
struct Edge {
    int u, v;
    void input() {
        cin >> u >> v;
    }
};
int n, e;
bool pos[mxn];
Edge edges[mxn];
 
 
namespace HLD {
 
    vector<int> g[mxn];
 
    struct Segtree {
        int n;
        vector<int> st, lz;

        Segtree() {};
        Segtree(int n) : n(n) {
            int m = MASK(lg(n));
            st.resize(m << 2, 0);
            lz.resize(m << 2, -1);
        }
        void setUpd(int i, int l, int r, int x) {
            st[i] = (r - l + 1) * x;
            lz[i] = x; 
            return;
        }
        void down(int i, int l, int r) {
            if (lz[i] == -1) return;
            int m = (l + r) >> 1;
            setUpd(2 * i, l, m, lz[i]);
            setUpd(2 * i + 1, m + 1, r, lz[i]);
            lz[i] = -1;
        }
        void upd(int i, int l, int r, int u, int v, int x) {
            if (l > v || r < u) return;
            if (l >= u && r <= v) {
                return setUpd(i, l, r, x);
            }
            down(i, l, r);
            int m = (l + r) >> 1;
            upd(2 * i, l, m, u, v, x);
            upd(2 * i + 1, m + 1, r, u, v, x);
            st[i] = st[2 * i] + st[2 * i + 1];
            return;
        }
        void upd(int u, int v, int x) {
            return upd(1, 1, n, u, v, x);
        }
        int get(int i, int l, int r, int u, int v) {
            if (l > v || r < u) return 0;
            if (l >= u && r <= v) return st[i];
            down(i, l, r);
            int m = (l + r) >> 1;
            int L = get(2 * i, l, m, u, v);
            int R = get(2 * i + 1, m + 1, r, u, v);
            return L + R;
        }
        int get(int u, int v) {
            return get(1, 1, n, u, v);
        }
        int find(int i, int l, int r, int u, int v) {
            if (l > v || r < u) return -1;
            if (l >= u && r <= v) return walk(i, l, r);
            down(i, l, r);
            int m = (l + r) >> 1;
            int R = find(2 * i + 1, m + 1, r, u, v);
            if (R != -1) return R;
            return find(2 * i, l, m, u, v);
        }
        int find(int u, int v) {
            return find(1, 1, n, u, v);
        }
        int walk(int i, int l, int r) {
            if (st[i] == (r - l + 1))
                return -1;
            for (; ;) {
                down(i, l, r);
                if (l == r) return l;
                if (l + 1 == r) return !st[2 * i + 1] ? r : l;
                int m = (l + r) >> 1;
                if (st[2 * i + 1] != (r - m)) {
                    l = m + 1;
                    i = 2 * i + 1;
                }
                else {
                    r = m;
                    i = 2 * i;
                }
            }
        }
    };
 
    int h[mxn];
    int par[mxn][lg + 1];
 
    int id[mxn], childs[mxn];
 
    void dfs(int u = 1, int p = 0) {
        childs[u] = 1;
        for (int i = 1; i <= lg; ++i)
            par[u][i] = par[par[u][i-1]][i-1];
 
        for (int v : g[u]) if (v != p) {
            h[v] = h[u] + 1;
            par[v][0] = u;
            dfs(v, u);
            childs[u] += childs[v];
        }
 
        return;
    }
    int find_ancestor(int u, int k) {
        for (; k; k -= k & -k)
            u = par[u][ctz(k)];
        return u;
    }
    int lca(int u, int v) {
        if (h[u] < h[v])
            swap(u, v);
        u = find_ancestor(u, h[u] - h[v]);
        if (u == v) return u;
        for (int i = lg(h[u]); i >= 0; --i) if (par[u][i] != par[v][i]) {
            u = par[u][i]; v = par[v][i];
        }
        return par[u][0];
    }

    int hld = 0, timer = 0;
    int head[mxn], path[mxn], order[mxn], node[mxn];

    void calc(int u = 1, int p = 0) {
        if (!head[hld]) {
            head[hld] = u;
        }
        path[u] = hld;
        order[u] = ++timer;
        node[timer] = u;

        int mx = -1, c = -1;
        for (int v : g[u]) if (v != p) {
            if (maximize(mx, childs[v]))
                c = v;
        }
        if (c != -1)
            calc(c, u);

        for (int v : g[u]) if (v != p && v != c) {
            hld++; calc(v, u);
        }

        return;
    }
    
    Segtree st;
    int value[mxn];
 
    vector<int> nodes;

    void query_get(int u, int p) {
        // cout << u << ' ' << p << '\n';
        while (u != par[p][0]) {
            int hd = path[u] != path[p] ? head[path[u]] : p;
            // cerr << hd << '\n';
            if (st.get(order[hd], order[u]) == order[u] - order[hd] + 1) {
                u = par[hd][0];
            }
            else {
                int pos = st.find(order[hd], order[u]);
                // cout << pos << ' ' << node[pos] << ' ' << order[hd] << ' ' << order[u] << '\n';
                nodes.push_back(id[ node[pos] ]);
                u = par[node[pos]][0];
            }
            // break;
        }
        return;
    }  
    void query_upd(int u, int p) {
        while (true) {
            if (path[u] == path[p]) {
                st.upd(order[p], order[u], 1);
                return;
            }
            else {
                int hd = head[path[u]];
                st.upd(order[hd], order[u], 1);
                u = par[hd][0];
            }
        }
        return;
    } 
    void getPath(int u, int v) {
        nodes.clear();
        int p = lca(u, v);
        if (u != p) query_get(u, find_ancestor(u, h[u] - h[p] - 1));
        if (v != p) query_get(v, find_ancestor(v, h[v] - h[p] - 1));
        sort(all(nodes));
    }
 
    void updPath(int u, int v, int x) {
        int p = lca(u, v);
        if (u != p) query_upd(u, find_ancestor(u, h[u] - h[p] - 1));
        if (v != p) query_upd(v, find_ancestor(v, h[v] - h[p] - 1));
        return;
    }   
 
    void build() {
 
        for (int i = 1; i <= e; ++i) if (pos[i]) {
            int u = edges[i].u, v = edges[i].v;
            g[u].push_back(v); g[v].push_back(u);
        }
 
        dfs(); 
        for (int i = 1; i <= e; ++i) if (pos[i]) {
            int u = edges[i].u, v = edges[i].v;
            if (par[u][0] != v) swap(u, v);
            id[u] = i;
        }
        calc();
        st = Segtree(timer);
 
        return;
    }
}
 
void solve() {
    cin >> n >> e;
    for (int i = 1; i <= e; ++i) 
        edges[i].input();
    for (int i = 1; i < n; ++i) {
        int p; cin >> p;
        pos[p] = true;
    }
 
    HLD::build(); 
 
    set<int> s;
    for (int i = 1; i <= e; ++i)
        s.insert(i);
    int cnt = 0;
    vector<int> ans(e+1);
 
    vector<int> assigned(e+1);
 
    for (int i = 1; i <= e; ++i) {
        int u = edges[i].u, v = edges[i].v;
        // cout << "PHASE i = " << i << "\n";
        // for (int i = 1; i <= e; ++i) if (pos[i])
        //     cout << HLD::value[edges[i].v] << ' ';
        // cout << '\n';
        // cout << u << ' ' << v << '\n';
        // cerr << i << ' '; 
        if (pos[i]) {
            // cout <<
            // cout << i << ' ' << HLD::getPath(v, v) << '\n';
            if (ans[i]) continue;
            ans[i] = ++cnt;
            HLD::updPath(u, v, 1);
        }
        else {
            // cout << "THREE\n";
            HLD::getPath(u, v);
            // cout << i << ": ";
            for (int num : HLD::nodes) {
                ans[num] = ++cnt;
                // cout << num << ' ';
            }
            // cout << '\n';

            ans[i] = ++cnt;
            HLD::updPath(u, v, 1);
        }
        // break;
        // cout << "PHASE END:\n\n";
    }
 
    for (int i = 1; i <= e; ++i)
        cout << ans[i] << ' ';
 
    return;
}
 
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    #define TASK "task"
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
 
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

Compilation message

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:340:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  340 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:341:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  341 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 6 ms 10076 KB Output is correct
5 Correct 4 ms 10124 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 32460 KB Output is correct
2 Correct 174 ms 42856 KB Output is correct
3 Correct 208 ms 35292 KB Output is correct
4 Correct 267 ms 78528 KB Output is correct
5 Correct 289 ms 81676 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 44244 KB Output is correct
2 Correct 156 ms 26960 KB Output is correct
3 Correct 91 ms 18788 KB Output is correct
4 Correct 104 ms 35792 KB Output is correct
5 Correct 35 ms 19792 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 75204 KB Output is correct
2 Correct 188 ms 87472 KB Output is correct
3 Correct 53 ms 32464 KB Output is correct
4 Correct 75 ms 42828 KB Output is correct
5 Correct 207 ms 96952 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 55044 KB Output is correct
2 Correct 122 ms 40396 KB Output is correct
3 Correct 400 ms 83280 KB Output is correct
4 Correct 345 ms 77140 KB Output is correct
5 Correct 23 ms 16208 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 6 ms 10076 KB Output is correct
5 Correct 4 ms 10124 KB Output is correct
6 Correct 4 ms 10076 KB Output is correct
7 Correct 6 ms 9820 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 86 ms 32460 KB Output is correct
10 Correct 174 ms 42856 KB Output is correct
11 Correct 208 ms 35292 KB Output is correct
12 Correct 267 ms 78528 KB Output is correct
13 Correct 289 ms 81676 KB Output is correct
14 Correct 181 ms 44244 KB Output is correct
15 Correct 156 ms 26960 KB Output is correct
16 Correct 91 ms 18788 KB Output is correct
17 Correct 104 ms 35792 KB Output is correct
18 Correct 35 ms 19792 KB Output is correct
19 Correct 168 ms 75204 KB Output is correct
20 Correct 188 ms 87472 KB Output is correct
21 Correct 53 ms 32464 KB Output is correct
22 Correct 75 ms 42828 KB Output is correct
23 Correct 207 ms 96952 KB Output is correct
24 Correct 216 ms 55044 KB Output is correct
25 Correct 122 ms 40396 KB Output is correct
26 Correct 400 ms 83280 KB Output is correct
27 Correct 345 ms 77140 KB Output is correct
28 Correct 23 ms 16208 KB Output is correct
29 Correct 524 ms 78264 KB Output is correct
30 Correct 509 ms 79224 KB Output is correct
31 Correct 401 ms 80920 KB Output is correct
32 Correct 290 ms 34380 KB Output is correct
33 Correct 322 ms 81320 KB Output is correct