Submission #1126998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126998		hphehe	Rigged Roads (NOI19_riggedroads)	C++20	29 / 100	337 ms	60804 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 5, LOG = 19;
vector<pii> adj[N];
pii edge[N];
int n, m;

namespace sub_full{
int up[N][LOG], in[N], out[N], h[N];
int fen[N], label[N]; /// the index of the EDGE
bool vis[N];

void upd(int id, int val){
    for(; id <= n; id += id & -id) fen[id] += val;
}
void upd(int l, int r, int val){
    upd(l, val);
    upd(r + 1, -val);
}

int get(int id){
    int ans = 0;
    for(; id > 0; id -= id & -id) ans += fen[id];
    return ans;
}

int timer = 0;
void dfs(int u, int p = 0){
    in[u] = ++timer;
    up[u][0] = p;
    h[u] = h[p] + 1;
    for(pii it : adj[u]){
        int v = it.fi, id = it.se;
        if(v != p){
            label[v] = id;
            dfs(v, u);
        }
    }
    out[u] = timer;
    upd(in[u], out[u], 1);
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int dif = h[u] - h[v];
    FOR(i, LOG) if(dif & (1 << i)) u = up[u][i];
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; --i)
        if(up[u][i] != up[v][i])
            u = up[u][i], v = up[v][i];
    return up[u][0];
}

/// ham get(u) tra ve so luong node available tu 1 -> u
/// so luong node tu u -> v = get(u) - get(par(v))

vi go_up(int u, int v){ /// go up from u -> v
    vi ans;
    while(h[u] > h[v]){
        int id = label[u];
        if(!vis[id]){
            ans.push_back(id);
            vis[id] = 1;
            upd(in[u], out[u], -1);
            u = up[u][0];
            continue;
        }
        for(int i = LOG - 1; i >= 0; --i){
            int nxt = up[u][i];
            if(nxt != 0 && get(u) - get(up[nxt][0]) == 0)
                u = nxt;
        }
        u = up[u][0];
    }
    return ans;
}

void go(){
    dfs(1);
    for(int k = 1; k < LOG; ++k)
        for(int i = 1; i <= n; ++i)
            up[i][k] = up[up[i][k - 1]][k - 1];
    int mex = 0;
    vi ans(m + 1);
    for(int i = 1; i <= m; ++i){
        int u = edge[i].fi, v = edge[i].se;
        if(h[u] < h[v]) swap(u, v);
        if(up[u][0] == v){
            assert(label[u] == i);
            if(!vis[label[u]]){
                ans[i] = ++mex;
                vis[i] = 1;
                upd(in[u], out[u], -1);
            }
            continue;
        }
        int p = lca(u, v);
        vi id, id2;
        if(u != p) id = go_up(u, p);
        if(v != p) id2 = go_up(v, p);
        for(int u : id2) id.push_back(u);
        sort(all(id));
        for(int u : id) ans[u] = ++mex;
        ans[i] = ++mex;
    }
    for(int i = 1; i <= m; ++i) cout << ans[i] << " ";
}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
    }
    FOR(i, n - 1){
        int id; cin >> id;
        int u = edge[id].fi, v = edge[id].se;
        adj[u].emplace_back(v, id);
        adj[v].emplace_back(u, id);
    }
    sub_full::go();
    return 0;
}
/**
4 5
3 4
1 2
2 3
1 3
1 4
2 4 5

4 4
1 2
1 4
2 3
3 4
1 3
**/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 32