Submission #1012970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012970		TrinhKhanhDung	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	402 ms	69312 KiB

riggedroads

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 3e5 + 10, LOG = 19;

int N, M;
pair<int, int> edges[MAX];
vector<pair<int, int>> adj[MAX];
int d[MAX][LOG], h[MAX], mark[MAX], ans[MAX], in[MAX], ou[MAX], edgeID[MAX], verID[MAX], timer;

int tree[MAX];

void update(int p, int c){
    while(p <= N){
        tree[p] += c;
        p += p & -p;
    }
}

int getVal(int p){
    int ans = 0;
    while(p){
        ans += tree[p];
        p -= p & -p;
    }
    return ans;
}

void dfs(int u, int p){
    h[u] = h[p] + 1;
    d[u][0] = p;
    for(int i=1; i<LOG; i++){
        d[u][i] = d[d[u][i - 1]][i - 1];
    }
    in[u] = ++timer;
    for(auto o: adj[u]){
        int v = o.fi;
        int id = o.se;
        if(v == p) continue;
        edgeID[v] = id;
        verID[id] = v;
        dfs(v, u);
    }
    ou[u] = timer;
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int delta = h[u] - h[v];
    for(int i=0; i<LOG; i++) if(BIT(delta, i)){
        u = d[u][i];
    }
    if(u == v) return u;
    for(int i=LOG-1; i>=0; i--) if(d[u][i] != d[v][i]){
        u = d[u][i];
        v = d[v][i];
    }
    return d[u][0];
}

vector<int> node;

void path(int a, int u){
    while(true){
        int val = getVal(in[u]);
        for(int i=LOG-1; i>=0; i--) if(val == getVal(in[d[u][i]])){
            u = d[u][i];
        }
        if(in[u] <= in[a] && ou[u] >= ou[a]) break;
        node.push_back(edgeID[u]);
        update(in[u], -1);
        update(ou[u] + 1, 1);
        u = d[u][0];
        if(getVal(in[u]) == 0) break;
    }
}

void road(int u, int v){
    int a = lca(u, v);
    path(a, u);
    path(a, v);
}

void solve(){
    cin >> N >> M;
    for(int i=1; i<=M; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = make_pair(u, v);
    }
    for(int i=1; i<N; i++){
        int u; cin >> u;
        mark[u] = true;
        adj[edges[u].fi].push_back(make_pair(edges[u].se, u));
        adj[edges[u].se].push_back(make_pair(edges[u].fi, u));
    }

    dfs(1, 0);
//    for(int i=1; i<=N; i++){
//        cout << in[i] << ' ' << ou[i] << ' ' << verID[edgeID[i]] << '\n';
//    }
    for(int i=1; i<=N; i++){
        update(in[i], 1);
        update(ou[i] + 1, -1);
    }
    int cur = 0;
    for(int i=1; i<=M; i++){
        if(mark[i]){
            if(ans[i] != 0) continue;
            ans[i] = ++cur;
            int u = verID[i];
            update(in[u], -1);
            update(ou[u] + 1, 1);
        }
        else{
            node.clear();
            road(edges[i].fi, edges[i].se);
            sort(ALL(node));
            for(int j: node){
                ans[j] = ++cur;
            }
            ans[i] = ++cur;
        }
    }

    for(int i=1; i<=M; i++){
        cout << ans[i] << ' ';
    }
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("split.inp", "r", stdin);
//    freopen("split.out", "w", stdout);

    int tt = 1;
//    cin >> tt;

    while(tt--){
        solve();
    }

    return 0;
}

• 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