Submission #1095928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095928		Sunbae	Rigged Roads (NOI19_riggedroads)	C++17	68 / 100	307 ms	106576 KiB

riggedroads

#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 (stderr)

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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 0 / 32