Submission #1095948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095948		Sunbae	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	271 ms	109168 KiB

riggedroads

#include <cstdio>
#include <vector>
#include <algorithm>
#define F first
#define S second
using namespace std;
const int N = 3e5 + 5, M = 6e5 + 5, MX = 12e5 + 5;
vector<int> g[N];
pair<int,int> Edge[N]; 
tuple<int,int,int> V[N];
int ch[N], sz[N], dep[N], up[N], pos[N], top[N], mn[N], idx[N], A[N], E[M], T[M], ST[M][20], s[MX], ti, mm, n, m, val, L, R, lca;
void init(int ind, int low, int high){
    s[ind] = m;
    if(low == high){ idx[low] = ind; return;}
    int mid = low + ((high-low)>>1);
    init(ind<<1, low, mid); init(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);
}
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); sz[u] += sz[v];
        E[mm++] = u;
        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);
    }
}
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 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].F, v = Edge[j].S;
        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]);
    init(1, 0, n-1); 
    for(int i = 0; i<m; ++i){
        if(dep[Edge[i].F] > dep[Edge[i].S]) swap(Edge[i].F, Edge[i].S);
        if(!ch[i]) lca = get_lca(Edge[val = i].F, Edge[i].S), UPD(Edge[i].F, Edge[i].S);
    }
    for(int i = 0; i<m; ++i){
        int u = Edge[i].F, v = Edge[i].S;
        if(ch[val = 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:75:13: warning: unused variable 'u' [-Wunused-variable]
   75 |         int u = Edge[i].F, v = Edge[i].S;
      |             ^
riggedroads.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
riggedroads.cpp:59:41: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     for(int i = 0, u, v; i<m; ++i) scanf("%d %d", &u, &v), Edge[i] = {--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 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32