oj.uz

Submission #369270

# Submission time Handle Problem Language Result Execution time Memory
369270 2021-02-21T05:24:23 Z Berted Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 530 ms 76468 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21484 KB Output is correct
2 Correct 15 ms 21484 KB Output is correct
3 Correct 15 ms 21484 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21484 KB Output is correct
2 Correct 15 ms 21484 KB Output is correct
3 Correct 15 ms 21484 KB Output is correct
4 Correct 15 ms 21612 KB Output is correct
5 Correct 16 ms 21612 KB Output is correct
6 Correct 15 ms 21740 KB Output is correct
7 Correct 15 ms 21612 KB Output is correct
8 Correct 16 ms 21612 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 35552 KB Output is correct
2 Correct 153 ms 41696 KB Output is correct
3 Correct 109 ms 31976 KB Output is correct
4 Correct 197 ms 60672 KB Output is correct
5 Correct 207 ms 62548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 46380 KB Output is correct
2 Correct 79 ms 32108 KB Output is correct
3 Correct 45 ms 26988 KB Output is correct
4 Correct 99 ms 39660 KB Output is correct
5 Correct 48 ms 28908 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 66796 KB Output is correct
2 Correct 451 ms 75120 KB Output is correct
3 Correct 100 ms 36460 KB Output is correct
4 Correct 157 ms 44012 KB Output is correct
5 Correct 494 ms 76468 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 54336 KB Output is correct
2 Correct 176 ms 44396 KB Output is correct
3 Correct 500 ms 70432 KB Output is correct
4 Correct 458 ms 66884 KB Output is correct
5 Correct 36 ms 25324 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21484 KB Output is correct
2 Correct 15 ms 21484 KB Output is correct
3 Correct 15 ms 21484 KB Output is correct
4 Correct 15 ms 21612 KB Output is correct
5 Correct 16 ms 21612 KB Output is correct
6 Correct 15 ms 21740 KB Output is correct
7 Correct 15 ms 21612 KB Output is correct
8 Correct 16 ms 21612 KB Output is correct
9 Correct 82 ms 35552 KB Output is correct
10 Correct 153 ms 41696 KB Output is correct
11 Correct 109 ms 31976 KB Output is correct
12 Correct 197 ms 60672 KB Output is correct
13 Correct 207 ms 62548 KB Output is correct
14 Correct 130 ms 46380 KB Output is correct
15 Correct 79 ms 32108 KB Output is correct
16 Correct 45 ms 26988 KB Output is correct
17 Correct 99 ms 39660 KB Output is correct
18 Correct 48 ms 28908 KB Output is correct
19 Correct 388 ms 66796 KB Output is correct
20 Correct 451 ms 75120 KB Output is correct
21 Correct 100 ms 36460 KB Output is correct
22 Correct 157 ms 44012 KB Output is correct
23 Correct 494 ms 76468 KB Output is correct
24 Correct 295 ms 54336 KB Output is correct
25 Correct 176 ms 44396 KB Output is correct
26 Correct 500 ms 70432 KB Output is correct
27 Correct 458 ms 66884 KB Output is correct
28 Correct 36 ms 25324 KB Output is correct
29 Correct 491 ms 66148 KB Output is correct
30 Correct 530 ms 65988 KB Output is correct
31 Correct 486 ms 63064 KB Output is correct
32 Correct 110 ms 32364 KB Output is correct
33 Correct 468 ms 64128 KB Output is correct