Submission #363744

#	Time	Username	Problem	Language	Result	Execution time	Memory
363744		shivensinha4	Rigged Roads (NOI19_riggedroads)	C++17	28 / 100	654 ms	175304 KiB

riggedroads

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'

vi depth, tin, ans;
vector<ii> tour, edge;
vector<vector<ii>> adj;
int pt = 1;

void dfs(int p) {
	tin[p] = tour.size();
	tour.push_back({depth[p], p});
	for (auto &i: adj[p]) if (i[0] != edge[p][0]) {
		depth[i[0]] = depth[p]+1;
		edge[i[0]] = {p, i[1]};
		dfs(i[0]);
		tour.push_back({depth[p], p});
	}
}

class SparseTable {
	vector<vector<ii>> st;
	int n;
	
	void buildTable(vector<ii> &raw) {
		int k = __lg(n)+1;
		st.resize(n, vector<ii> (k));
		for_(i, 0, n) st[i][0] = raw[i];
		for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1)
				st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
	}

public:
	void build(vector<ii> &nums) {
		n = nums.size();
		buildTable(nums);
	}
	
	int mn(int l, int r) {
		if (l > r) swap(l, r);
		int p = __lg(r-l+1);
		return min(st[l][p], st[r - (1<<p) + 1][p])[1];
	}
};

SparseTable st;

class UFDS {
public:
	vi p, rank; int count = 0;
	
	void build(int n) {
		p.resize(n); rank.resize(n); edge.resize(n);
		for_(i, 0, n) p[i] = i;
		count = n;
	}
	int getParent(int i) {
		return (p[i] == i) ? i : (p[i] = getParent(p[i]));
	}
	void join(int i, int j) {
		int a = getParent(i), b = getParent(j);
		if (a == b) return;
		count -= 1;
		edge[a] = edge[b] = (depth[edge[a][0]] < depth[edge[b][0]]) ? edge[a] : edge[b];
		if (rank[a] > rank[b]) {
			p[b] = a;
		} else {
			p[a] = b;
			if (rank[a] == rank[b]) rank[b] += 1;
		}
	}
};

UFDS ufds;

void up(int a, int p) {
	vi path;
	a = ufds.getParent(a);
	while (a != ufds.getParent(p)) {
		path.push_back(edge[a][1]);
		ufds.join(edge[a][0], a);
		a = ufds.getParent(a);
	}
	sort(path.begin(), path.end());
	for (auto i: path) ans[i] = pt++;
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m; cin >> n >> m;
	depth.resize(n); tin.resize(n); adj.resize(n); edge.resize(n); ans.resize(m, -1);
	vector<ii> edges(m);
	for_(i, 0, m) {
		cin >> edges[i][0] >> edges[i][1];
		edges[i][0] -= 1; edges[i][1] -= 1;
	}
	
	vi req(n-1);
	vector<bool> marked(m);
	for_(i, 0, n-1) {
		cin >> req[i];
		req[i] -= 1;
		marked[req[i]] = true;
		adj[edges[req[i]][0]].push_back({edges[req[i]][1], req[i]});
		adj[edges[req[i]][1]].push_back({edges[req[i]][0], req[i]});
	}
	
	dfs(0);
	st.build(tour);
	ufds.build(n);
	
	for_(i, 0, m) {
		if (marked[i]) {
			if (ans[i] == -1) {
				ans[i] = pt++;
				ufds.join(edges[i][0], edges[i][1]);
			}
		} else {
			int lc = st.mn(tin[edges[i][0]], tin[edges[i][1]]);
			up(edges[i][0], lc);
			up(edges[i][1], lc);
			ans[i] = pt++;
		}
	}
	
	for (auto i: ans) cout << i << " ";
	cout << endl;
	
	return 0;
}

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