oj.uz

Submission #1084227

# Submission time Handle Problem Language Result Execution time Memory
1084227 2024-09-05T16:24:44 Z anhthi Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 488 ms 97220 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 10844 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 5 ms 11100 KB Output is correct
6 Correct 5 ms 11200 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 35016 KB Output is correct
2 Correct 191 ms 46444 KB Output is correct
3 Correct 251 ms 36436 KB Output is correct
4 Correct 288 ms 79112 KB Output is correct
5 Correct 314 ms 82112 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 47588 KB Output is correct
2 Correct 142 ms 29636 KB Output is correct
3 Correct 69 ms 20560 KB Output is correct
4 Correct 128 ms 38604 KB Output is correct
5 Correct 40 ms 21328 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 78792 KB Output is correct
2 Correct 235 ms 88016 KB Output is correct
3 Correct 61 ms 33700 KB Output is correct
4 Correct 91 ms 43860 KB Output is correct
5 Correct 258 ms 97220 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 58832 KB Output is correct
2 Correct 126 ms 43248 KB Output is correct
3 Correct 399 ms 86932 KB Output is correct
4 Correct 358 ms 77664 KB Output is correct
5 Correct 24 ms 17240 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10844 KB Output is correct
2 Correct 4 ms 10844 KB Output is correct
3 Correct 4 ms 10844 KB Output is correct
4 Correct 4 ms 11100 KB Output is correct
5 Correct 5 ms 11100 KB Output is correct
6 Correct 5 ms 11200 KB Output is correct
7 Correct 5 ms 11100 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 93 ms 35016 KB Output is correct
10 Correct 191 ms 46444 KB Output is correct
11 Correct 251 ms 36436 KB Output is correct
12 Correct 288 ms 79112 KB Output is correct
13 Correct 314 ms 82112 KB Output is correct
14 Correct 171 ms 47588 KB Output is correct
15 Correct 142 ms 29636 KB Output is correct
16 Correct 69 ms 20560 KB Output is correct
17 Correct 128 ms 38604 KB Output is correct
18 Correct 40 ms 21328 KB Output is correct
19 Correct 214 ms 78792 KB Output is correct
20 Correct 235 ms 88016 KB Output is correct
21 Correct 61 ms 33700 KB Output is correct
22 Correct 91 ms 43860 KB Output is correct
23 Correct 258 ms 97220 KB Output is correct
24 Correct 240 ms 58832 KB Output is correct
25 Correct 126 ms 43248 KB Output is correct
26 Correct 399 ms 86932 KB Output is correct
27 Correct 358 ms 77664 KB Output is correct
28 Correct 24 ms 17240 KB Output is correct
29 Correct 487 ms 78984 KB Output is correct
30 Correct 488 ms 79840 KB Output is correct
31 Correct 404 ms 81616 KB Output is correct
32 Correct 338 ms 35412 KB Output is correct
33 Correct 404 ms 81744 KB Output is correct