Submission #369270

#	Time	Username	Problem	Language	Result	Execution time	Memory
369270		Berted	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	530 ms	76468 KiB

riggedroads

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define pii pair<int, int>
#define fst first
#define snd second
#define vi vector<int>
#define pub push_back

using namespace std;

int N, M, H[300001], sz[300001], Par[300001];
pii edges[300001];
vector<pii> adj[300001];
bool spec[300001];

int S = 0, h[300001], par[300001], id[300001];
set<pii> node[300001]; 

int A[300001], cur = 1;

void preDFS(int u, int p)
{
	sz[u] = 1;
	for (auto v : adj[u])
	{
		if (v.fst != p) 
		{
			Par[v.fst] = v.snd; H[v.fst] = H[u] + 1;
			preDFS(v.fst, u); 
			sz[u] += sz[v.fst];
		}
	}
}

void DFS(int u, int p)
{
	int hvy = -1;
	for (auto v : adj[u])
	{
		if (v.fst != p)
		{
			if (hvy == -1 || sz[v.fst] > sz[hvy]) {hvy = v.fst;}
		}
	}
	if (hvy != -1) {id[hvy] = id[u]; DFS(hvy, u);}
	for (auto v : adj[u])
	{
		if (v.fst != p && v.fst != hvy)
		{
			h[S] = h[id[u]] + 1;
			par[S] = u; id[v.fst] = S++;
			DFS(v.fst, u);
		}
	}
	//cerr << "DFS: " << u << " " << id[u] << " " << H[u] << "\n";
	node[id[u]].insert({H[u], u});
}

inline void Prise(vi& vec, int& v)
{
	while (node[id[v]].size() && node[id[v]].begin() -> fst <= H[v])
	{
		vec.push_back(Par[node[id[v]].begin() -> snd]);
		node[id[v]].erase(node[id[v]].begin());
	}
	v = par[id[v]];
}

inline void solve(int u, int v)
{
	//cerr << "S: " << u << " " << v << "\n";
	vi temp;
	if (h[id[u]] > h[id[v]]) {swap(u, v);}
	while (h[id[v]] > h[id[u]]) {Prise(temp, v);}
	while (id[v] != id[u]) {Prise(temp, u); Prise(temp, v);}
	//cerr << "Done\n";
	//cerr << "cur: " << u << " " << v << "\n";
	int L = min(H[u], H[v]), R = max(H[u], H[v]);
	//cerr << L << " " << R << "\n";
	auto it = node[id[u]].upper_bound({L, 1000000000});
	while (it != node[id[u]].end() && it -> fst <= R)
	{
		//cerr << " " << it -> snd << "\n";
		temp.push_back(Par[it -> snd]);
		it = node[id[u]].erase(it);
	}
	sort(temp.begin(), temp.end());
	for (const auto& x : temp) 
	{
		if (!A[x]) A[x] = cur++;
	}
	//cerr << "Done2\n";
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) 
	{
		cin >> edges[i].fst >> edges[i].snd;
		edges[i].fst--; edges[i].snd--;
	}
	for (int i = 1; i < N; i++)
	{
		int x; cin >> x; x--;
		spec[x] = 1;
		adj[edges[x].fst].push_back({edges[x].snd, x});
		adj[edges[x].snd].push_back({edges[x].fst, x});
	}
	S++; h[0] = 0; par[0] = -1; id[0] = 0; H[0] = 0; Par[0] = -1;
	preDFS(0, -1);
	DFS(0, -1);
	for (int i = 0; i < M; i++)
	{
		if (!spec[i]) {solve(edges[i].fst, edges[i].snd);}
		if (!A[i]) {A[i] = cur++;}
	}
	for (int i = 0; i < M; i++) 
	{
		cout << A[i];
		if (i + 1 < M) cout << " ";
	}
	cout << "\n";
	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