oj.uz

Submission #1095928

# Submission time Handle Problem Language Result Execution time Memory
1095928 2024-10-03T12:07:09 Z Sunbae Rigged Roads (NOI19_riggedroads) C++17
68 / 100
 307 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){
    s[ind] = m;
    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(m); ++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:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
riggedroads.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
riggedroads.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d", &j);
      |         ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10332 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 2 ms 8544 KB Output is correct
8 Correct 3 ms 10584 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 37396 KB Output is correct
2 Correct 121 ms 46960 KB Output is correct
3 Correct 142 ms 22460 KB Output is correct
4 Correct 187 ms 85220 KB Output is correct
5 Correct 199 ms 88240 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 49488 KB Output is correct
2 Correct 90 ms 25428 KB Output is correct
3 Correct 46 ms 18260 KB Output is correct
4 Correct 78 ms 37968 KB Output is correct
5 Correct 27 ms 22160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 89232 KB Output is correct
2 Correct 217 ms 99660 KB Output is correct
3 Correct 51 ms 34128 KB Output is correct
4 Correct 82 ms 48640 KB Output is correct
5 Correct 307 ms 106576 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 63256 KB Output is correct
2 Correct 87 ms 47816 KB Output is correct
3 Correct 244 ms 94032 KB Output is correct
4 Correct 215 ms 88144 KB Output is correct
5 Correct 17 ms 15804 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10332 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 2 ms 8544 KB Output is correct
8 Correct 3 ms 10584 KB Output is correct
9 Correct 68 ms 37396 KB Output is correct
10 Correct 121 ms 46960 KB Output is correct
11 Correct 142 ms 22460 KB Output is correct
12 Correct 187 ms 85220 KB Output is correct
13 Correct 199 ms 88240 KB Output is correct
14 Correct 108 ms 49488 KB Output is correct
15 Correct 90 ms 25428 KB Output is correct
16 Correct 46 ms 18260 KB Output is correct
17 Correct 78 ms 37968 KB Output is correct
18 Correct 27 ms 22160 KB Output is correct
19 Correct 192 ms 89232 KB Output is correct
20 Correct 217 ms 99660 KB Output is correct
21 Correct 51 ms 34128 KB Output is correct
22 Correct 82 ms 48640 KB Output is correct
23 Correct 307 ms 106576 KB Output is correct
24 Correct 225 ms 63256 KB Output is correct
25 Correct 87 ms 47816 KB Output is correct
26 Correct 244 ms 94032 KB Output is correct
27 Correct 215 ms 88144 KB Output is correct
28 Correct 17 ms 15804 KB Output is correct
29 Correct 291 ms 83064 KB Output is correct
30 Correct 250 ms 87376 KB Output is correct
31 Correct 233 ms 85980 KB Output is correct
32 Correct 135 ms 22668 KB Output is correct
33 Incorrect 227 ms 87120 KB Output isn't correct
34 Halted 0 ms 0 KB -