oj.uz

Submission #369277

# Submission time Handle Problem Language Result Execution time Memory
369277 2021-02-21T05:28:33 Z Berted Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 515 ms 76396 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 20 ms 21484 KB Output is correct
2 Correct 16 ms 21484 KB Output is correct
3 Correct 17 ms 21484 KB Output is correct

Subtask #2
19.0 / 19.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 35680 KB Output is correct
2 Correct 157 ms 41700 KB Output is correct
3 Correct 110 ms 31976 KB Output is correct
4 Correct 205 ms 60628 KB Output is correct
5 Correct 212 ms 62548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 46188 KB Output is correct
2 Correct 81 ms 32108 KB Output is correct
3 Correct 45 ms 26988 KB Output is correct
4 Correct 100 ms 39660 KB Output is correct
5 Correct 45 ms 28908 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 66796 KB Output is correct
2 Correct 426 ms 75104 KB Output is correct
3 Correct 100 ms 36460 KB Output is correct
4 Correct 158 ms 44172 KB Output is correct
5 Correct 479 ms 76396 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 54080 KB Output is correct
2 Correct 181 ms 44524 KB Output is correct
3 Correct 515 ms 70524 KB Output is correct
4 Correct 468 ms 67012 KB Output is correct
5 Correct 37 ms 25452 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 21484 KB Output is correct
2 Correct 16 ms 21484 KB Output is correct
3 Correct 17 ms 21484 KB Output is correct
4 Correct 15 ms 21740 KB Output is correct
5 Correct 16 ms 21740 KB Output is correct
6 Correct 15 ms 21740 KB Output is correct
7 Correct 18 ms 21612 KB Output is correct
8 Correct 16 ms 21704 KB Output is correct
9 Correct 77 ms 35680 KB Output is correct
10 Correct 157 ms 41700 KB Output is correct
11 Correct 110 ms 31976 KB Output is correct
12 Correct 205 ms 60628 KB Output is correct
13 Correct 212 ms 62548 KB Output is correct
14 Correct 133 ms 46188 KB Output is correct
15 Correct 81 ms 32108 KB Output is correct
16 Correct 45 ms 26988 KB Output is correct
17 Correct 100 ms 39660 KB Output is correct
18 Correct 45 ms 28908 KB Output is correct
19 Correct 386 ms 66796 KB Output is correct
20 Correct 426 ms 75104 KB Output is correct
21 Correct 100 ms 36460 KB Output is correct
22 Correct 158 ms 44172 KB Output is correct
23 Correct 479 ms 76396 KB Output is correct
24 Correct 294 ms 54080 KB Output is correct
25 Correct 181 ms 44524 KB Output is correct
26 Correct 515 ms 70524 KB Output is correct
27 Correct 468 ms 67012 KB Output is correct
28 Correct 37 ms 25452 KB Output is correct
29 Correct 492 ms 66024 KB Output is correct
30 Correct 510 ms 65988 KB Output is correct
31 Correct 492 ms 62936 KB Output is correct
32 Correct 115 ms 32364 KB Output is correct
33 Correct 467 ms 63992 KB Output is correct