Submission #1252131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252131		pinbu	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	245 ms	58508 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;

const int NM = 300005;

int n, m; array<int, 2> e[NM]; bool s[NM];

vector<array<int, 2>> adj[NM];
int id[NM];
int h[NM], up[NM][19];
void DFS(int u, int p) {
	for (auto [v, i]: adj[u]) if (v ^ p) {
		h[v] = h[u] + 1;
		id[v] = i;
		up[v][0] = u;
		for (int k = 1; k < 19; k++) up[v][k] = up[up[v][k - 1]][k - 1];
		DFS(v, u);
	}
}
int LCA(int u, int v) {
	if (h[u] < h[v]) swap(u, v);
	while (h[u] > h[v]) {
		int k = __builtin_ctz(h[u] - h[v]);
		u = up[u][k];
	}
	if (u == v) return u;
	for (int k = 18; k >= 0; k--) if (up[u][k] ^ up[v][k]) {
		u = up[u][k], v = up[v][k];
	}
	return up[u][0];
}

int par[NM];
int findp(int u) {
	return u ^ par[u] ? par[u] = findp(par[u]) : u;
}
void unite(int u, int v) {
	u = findp(u), v = findp(v);
	par[v] = u;
}

int ans[NM];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
    	cin >> u >> v;
    	e[i] = {u, v};
    }
    for (int i = 1, j; i < n; i++) {
    	cin >> j; s[j] = true;
    	adj[e[j][0]].push_back({e[j][1], j});
    	adj[e[j][1]].push_back({e[j][0], j});
    }
    h[1] = 0; DFS(1, 1);
    
    iota(par + 1, par + 1 + n, 1);
    int mex = 0;
    for (int i = 1; i <= m; i++) {
    	if (!ans[i]) {
    		if (s[i]) {
    			ans[i] = ++mex;
    			auto [u, v] = e[i];
    			if (h[u] > h[v]) swap(u, v);
    			unite(u, v);
    		} else {
	    		vector<int> cands;
	    		auto [u, v] = e[i];
	    		int lca = LCA(u, v);
	    		while (true) {
	    			u = findp(u), v = findp(v);
	    			if (h[u] < h[v]) swap(u, v);
	    			if (h[u] <= h[lca]) break;
	    			unite(up[u][0], u);
	    			cands.emplace_back(id[u]);
	    			u = up[u][0];
	    		}
	    		sort(begin(cands), end(cands));
	    		for (int idx: cands) ans[idx] = ++mex;
	    		ans[i] = ++mex;
	    	}
    	}
	    cout << ans[i] << ' ';
    }
    
    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