Submission #1252139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252139		pinbu	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	210 ms	37408 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], up0[NM];
void DFS(int u, int p) {
	for (auto [v, i]: adj[u]) if (v ^ p) {
		h[v] = h[u] + 1;
		id[v] = i;
		up0[v] = u;
		DFS(v, u);
	}
}

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];
	    		v = findp(v);
	    		while (true) {
	    			u = findp(u);
	    			if (u == v) break;
	    			if (h[u] < h[v]) swap(u, v);
	    			unite(up0[u], u);
	    			cands.emplace_back(id[u]);
	    			u = up0[u];
	    		}
	    		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