oj.uz

Submission #996790

# Submission time Handle Problem Language Result Execution time Memory
996790 2024-06-11T08:20:30 Z LOLOLO Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 335 ms 68808 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 10;
vector <pair <int, int>> ed[N];
int p[N][19], in[N], ou[N], timer = 0, id[N], cc = 1, a[N], b[N], used[N], w[N], f[N], rev[N];

void dfs(int u, int v) {
    p[u][0] = v;
    for (int j = 1; j < 19; j++) {
        p[u][j] = p[p[u][j - 1]][j - 1];
    }

    timer++;
    in[u] = timer; 
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        id[x.f] = x.s;
        rev[x.s] = x.f;
        dfs(x.f, u);
    }

    ou[u] = timer;
}

bool is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= ou[b]; 
}

int lca(int a, int b) {
    if (is(a, b))
        return a;

    if (is(b, a))
        return b;

    for (int j = 18; j >= 0; j--) {
        if (is(p[a][j], b) == 0)
            a = p[a][j];
    }

    return p[a][0];
}

void upd(int i, int x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}

int get(int i) {
    i = in[i];
    int s = 0;
    for (; i; i -= i & (-i))
        s += f[i];

    return s;
}

vector <int> lst;
void path(int a, int c) {
    while (1) {
        int val = get(a);
        for (int j = 18; j >= 0; j--) {
            if (get(p[a][j]) == val)
                a = p[a][j];
        }

        if (is(a, c))
            break;

        lst.pb(id[a]);
        upd(in[a], -1);
        upd(ou[a] + 1, 1);
        a = p[a][0];
    }
}

void road(int a, int b) {
    int c = lca(a, b);
    path(a, c);
    path(b, c);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    in[0] = 0;
    ou[0] = 1e9;
    int n, e;
    cin >> n >> e;

    for (int i = 1; i <= e; i++) {
        cin >> a[i] >> b[i];
    }

    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        used[x] = 1;
        ed[a[x]].pb({b[x], x});
        ed[b[x]].pb({a[x], x});
    }

    dfs(1, 0);

    for (int i = 2; i <= n; i++) {
        upd(in[i], 1);
        upd(ou[i] + 1, -1);
    }

    for (int i = 1; i <= e; i++) {
        if (used[i] == 0) {
            road(a[i], b[i]);
            sort(all(lst));
            for (auto x : lst) {
                w[x] = cc++;
            }

            lst.clear();
        }

        if (w[i] == 0) {
            w[i] = cc++;
            if (used[i]) {
                upd(in[rev[i]], -1);
                upd(ou[rev[i]] + 1, 1);
            }
        }

        cout << w[i] << " ";
    }
    
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 32456 KB Output is correct
2 Correct 96 ms 38792 KB Output is correct
3 Correct 120 ms 27336 KB Output is correct
4 Correct 116 ms 57016 KB Output is correct
5 Correct 117 ms 59176 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 38856 KB Output is correct
2 Correct 68 ms 29736 KB Output is correct
3 Correct 33 ms 24664 KB Output is correct
4 Correct 84 ms 35796 KB Output is correct
5 Correct 31 ms 27736 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 56756 KB Output is correct
2 Correct 218 ms 68808 KB Output is correct
3 Correct 53 ms 33748 KB Output is correct
4 Correct 60 ms 41544 KB Output is correct
5 Correct 231 ms 68288 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 46284 KB Output is correct
2 Correct 77 ms 39980 KB Output is correct
3 Correct 213 ms 64596 KB Output is correct
4 Correct 213 ms 62800 KB Output is correct
5 Correct 16 ms 25432 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 3 ms 21596 KB Output is correct
3 Correct 3 ms 21596 KB Output is correct
4 Correct 3 ms 21596 KB Output is correct
5 Correct 3 ms 21596 KB Output is correct
6 Correct 3 ms 21596 KB Output is correct
7 Correct 3 ms 21596 KB Output is correct
8 Correct 3 ms 21592 KB Output is correct
9 Correct 45 ms 32456 KB Output is correct
10 Correct 96 ms 38792 KB Output is correct
11 Correct 120 ms 27336 KB Output is correct
12 Correct 116 ms 57016 KB Output is correct
13 Correct 117 ms 59176 KB Output is correct
14 Correct 104 ms 38856 KB Output is correct
15 Correct 68 ms 29736 KB Output is correct
16 Correct 33 ms 24664 KB Output is correct
17 Correct 84 ms 35796 KB Output is correct
18 Correct 31 ms 27736 KB Output is correct
19 Correct 188 ms 56756 KB Output is correct
20 Correct 218 ms 68808 KB Output is correct
21 Correct 53 ms 33748 KB Output is correct
22 Correct 60 ms 41544 KB Output is correct
23 Correct 231 ms 68288 KB Output is correct
24 Correct 169 ms 46284 KB Output is correct
25 Correct 77 ms 39980 KB Output is correct
26 Correct 213 ms 64596 KB Output is correct
27 Correct 213 ms 62800 KB Output is correct
28 Correct 16 ms 25432 KB Output is correct
29 Correct 329 ms 61004 KB Output is correct
30 Correct 335 ms 62408 KB Output is correct
31 Correct 264 ms 59596 KB Output is correct
32 Correct 109 ms 27732 KB Output is correct
33 Correct 245 ms 60108 KB Output is correct