oj.uz

Submission #1095938

# Submission time Handle Problem Language Result Execution time Memory
1095938 2024-10-03T12:18:32 Z Sunbae Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 278 ms 106576 KB 
#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 3e5 + 5, M = 6e5 + 5;
vector<int> g[N];
pair<int,int> Edge[N];
tuple<int,int,int> V[N];
int sz[N], ti, pos[N], mn[N], ch[N], dep[N], mm, idx[N], A[N], top[N], up[N], ST[M][20], E[M], T[M], s[N<<2], n, m, L, R, val, lca;
void bld(int ind, int low, int high){
    if(low == high){ idx[low] = ind; return;}
    int mid = low + ((high-low)>>1);
    bld(ind<<1, low, mid); bld(ind<<1|1, mid+1, high);
}
void upd(int ind, int low, int high){
    if(low > R || high < L) return;
    if(L <= low && high <= R){ s[ind] = min(s[ind], val); return;}
    int mid = low + ((high-low)>>1);
    upd(ind<<1, low, mid); upd(ind<<1|1, mid+1, high);
}
int get_lca(int u, int v){
    if(mn[u] > mn[v]) swap(u, v);
    int j = 31 - __builtin_clz(mn[v] - mn[u] + 1);
    return T[min(ST[mn[u]][j], ST[mn[v]-(1<<j)+1][j])];
}
void dfs(int u){
    sz[E[mm++] = u] = 1;
    for(int& v: g[u]){
        g[v].erase(find(g[v].begin(), g[v].end(), up[v] = u));
        dep[v] = dep[u] + 1; dfs(v); 
        E[mm++] = u; sz[u] += sz[v];
        if(sz[v] > sz[g[u][0]]) swap(v, g[u][0]);
    }
}
void efs(int u){
    pos[u] = ti++;
    for(int v: g[u]){
        top[v] = (v == g[u][0]) ? top[u] : v;
        efs(v);
    }
}
void UPD(int u, int v){
    if(top[u] == top[v]){
        if(dep[u] > dep[v]) swap(u, v);
        L = pos[u] + (u == lca); R = pos[v];
        if(L <= R) upd(1, 0, n-1);
        return;
    }
    if(dep[top[u]] > dep[top[v]]) swap(u, v);
    L = pos[top[v]] + (top[v] == lca); R = pos[v];
    if(L <= R) upd(1, 0, n-1);
    UPD(u, up[top[v]]);
}
 
signed main(){
    scanf("%d %d", &n, &m);
    for(int i = 0, u, v; i<m; ++i){
        scanf("%d %d", &u, &v); 
        Edge[i] = {--u, --v};
    }
    for(int i = 0, j; i<n-1; ++i){
        scanf("%d", &j); ch[--j] = 1;
        int u = Edge[j].first, v = Edge[j].second;
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs(0); efs(0);
    for(int i = mm-1; i>=0; --i) T[mn[E[i]] = i] = E[i];
    for(int i = 0; i<mm; ++i) ST[i][0] = mn[E[i]];
    for(int j = 1; j<32 - __builtin_clz(mm); ++j) for(int i = 0; i+(1<<j)-1<mm; ++i) ST[i][j] = min(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);
    fill(s, s+(n<<2), m);
    bld(1, 0, n-1);
    for(int i = 0; i<m; ++i){
        int u = Edge[i].first, v = Edge[i].second;
        if(!ch[i]){ val = i; lca = get_lca(u, v); UPD(u, v);}
    }
    for(int i = 0; i<m; ++i){
        int u = Edge[i].first, v = Edge[i].second;
        if(dep[u] > dep[v]) swap(u, v);
        val = i;
        if(ch[i]) for(int x = idx[pos[v]]; x; x>>=1) val = min(val, s[x]);
        V[i] = {val, !ch[i], i};
    }
    sort(V, V+m); 
    for(int i = ti = 0; i<m; ++i) A[get<2>(V[i])] = ++ti;
    for(int i = 0; i<m; ++i) printf("%d ", A[i]);
}

Compilation message

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
riggedroads.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
riggedroads.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d", &j); ch[--j] = 1;
      |         ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 35528 KB Output is correct
2 Correct 133 ms 45752 KB Output is correct
3 Correct 150 ms 21840 KB Output is correct
4 Correct 199 ms 84672 KB Output is correct
5 Correct 206 ms 88252 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 47748 KB Output is correct
2 Correct 78 ms 23632 KB Output is correct
3 Correct 45 ms 15960 KB Output is correct
4 Correct 85 ms 37172 KB Output is correct
5 Correct 26 ms 19544 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 88148 KB Output is correct
2 Correct 191 ms 99164 KB Output is correct
3 Correct 49 ms 33364 KB Output is correct
4 Correct 76 ms 46672 KB Output is correct
5 Correct 226 ms 106576 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 62500 KB Output is correct
2 Correct 86 ms 45648 KB Output is correct
3 Correct 238 ms 93776 KB Output is correct
4 Correct 222 ms 87400 KB Output is correct
5 Correct 20 ms 14936 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 4 ms 7768 KB Output is correct
5 Correct 4 ms 7772 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 3 ms 7772 KB Output is correct
9 Correct 69 ms 35528 KB Output is correct
10 Correct 133 ms 45752 KB Output is correct
11 Correct 150 ms 21840 KB Output is correct
12 Correct 199 ms 84672 KB Output is correct
13 Correct 206 ms 88252 KB Output is correct
14 Correct 111 ms 47748 KB Output is correct
15 Correct 78 ms 23632 KB Output is correct
16 Correct 45 ms 15960 KB Output is correct
17 Correct 85 ms 37172 KB Output is correct
18 Correct 26 ms 19544 KB Output is correct
19 Correct 183 ms 88148 KB Output is correct
20 Correct 191 ms 99164 KB Output is correct
21 Correct 49 ms 33364 KB Output is correct
22 Correct 76 ms 46672 KB Output is correct
23 Correct 226 ms 106576 KB Output is correct
24 Correct 148 ms 62500 KB Output is correct
25 Correct 86 ms 45648 KB Output is correct
26 Correct 238 ms 93776 KB Output is correct
27 Correct 222 ms 87400 KB Output is correct
28 Correct 20 ms 14936 KB Output is correct
29 Correct 278 ms 83144 KB Output is correct
30 Correct 270 ms 87124 KB Output is correct
31 Correct 270 ms 85904 KB Output is correct
32 Correct 140 ms 21840 KB Output is correct
33 Correct 234 ms 86868 KB Output is correct