Submission #1312315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312315		samarthkulkarni	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	550 ms	107568 KiB

riggedroads

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

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


struct DSU {
	ll n;
	vi rep, sz;
	DSU (ll _n) {
		n = _n;
		rep.resize(n+1);
		sz.resize(n+1, 1);
		iota(all(rep), 0);
	}

	int find(int a) {
		while (a != rep[a]) a = rep[a];
		return a;
	}

	bool isSame(int a, int b) {
		return find(a) == find(b);
	}

	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[a] < sz[b]) swap(a, b);
		rep[b] = a;
		sz[a] += sz[b];
	}
};


const int N = 3e5+10;
const int K = 25;
vi adj[N];
int prt[N];
int depth[N];
int BL[N][K];


void dfs(int a = 1, int p = 1) {
	for (auto b : adj[a]) {
		if (b == p) continue;
		prt[b] = a;
		depth[b] = depth[a]+1;
		dfs(b, a);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) swap(a, b);
	int k = depth[a] - depth[b];
	for (int j = K-1; j >= 0; j--) {
		if (k & (1 << j)) a = BL[a][j];
	}
	if (a == b) return a;

	for (int j = K-1; j >= 0; j--) {
		if (BL[a][j] != BL[b][j]) {
			a = BL[a][j];
			b = BL[b][j];
		}
	}

	return prt[a];
}


void solution() {
	ll n, m; cin >> n >> m;


	map<pr, int> e;
	vector<pr> edge(m+1);
	for (int i = 1; i <= m; i++) {
		cin >> edge[i].ff >> edge[i].ss;
		if (edge[i].ff > edge[i].ss) swap(edge[i].ff, edge[i].ss);
		e[{edge[i].ff, edge[i].ss}] = i;
	}

	set<ll> hs;
	for (int i = 0; i < n-1; i++) {
		ll x; cin >> x; hs.insert(x);
	}
	

	for (int i = 1; i <= m; i++) {
		if (hs.count(i)) {
			auto [u, v] = edge[i];
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
	}

	dfs();

	for (int j = 0; j < K; j++) {
		for (int i = 1; i <= n; i++) {
			if (j == 0) {BL[i][j] = prt[i]; continue;}
			BL[i][j] = BL[BL[i][j-1]][j-1];
		}
	}



	DSU d(n);

	vi res(m+1);
	ll p = 1;


	auto con = [&](int a, int b) {
		pr z = {a, b};
		if (z.ff > z.ss) swap(z.ff, z.ss);
		return z;
	};

	for (int i = 1; i <= m; i++) {
		if (res[i]) continue;
		else if (hs.count(i)) res[i] = p++;
		else {

			vi upd;
			auto [u, v] = edge[i];
			int k = lca(u, v);


			while (d.find(u) != d.find(k)) {
				upd.push_back(e[con(u, prt[u])]);
				d.unite(u, prt[u]);
				u = prt[u];
			}

			while (d.find(v) != d.find(k)) {
				upd.push_back(e[con(v, prt[v])]);
				d.unite(v, prt[v]);
				v = prt[v];
			}

			sort(all(upd));
			for (auto val : upd) {
				if (!res[val]) res[val] = p++;
			}

			res[i] = p++;
		}
	}

	for (int i = 1; i <= m; i++) {
		cout << (!res[i] ? p++ : res[i]) << " ";
	}



}

• 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