oj.uz

Submission #877190

# Submission time Handle Problem Language Result Execution time Memory
877190 2023-11-23T03:12:10 Z fanwen Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 363 ms 50204 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \

const int MAX = 3e5 + 5;
const int LOG = 18;

int N, M, ans[MAX], depth[MAX], numChild[MAX], local[MAX], par[MAX], header[MAX];
vector <int> adj[MAX], mst;
vector <pair <int, int>> edges;

void dfs(int u, int p) {
	numChild[u] = 1;
	par[u] = p;
	int Max = 0, id = 0;
	for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != p) {
		int v = adj[u][i];
		dfs(v, u);
		numChild[u] += numChild[v];
		if(Max < numChild[v]) {
			Max = numChild[v];
			id = i;
		}
	}
	swap(adj[u][id], adj[u][0]);
}

void HLD(int u) {
	static int run = 0;
	local[u] = ++run;
	for (int i = 0; i < (int) adj[u].size(); ++i) if(adj[u][i] != par[u]) {
		int v = adj[u][i];
		if(i == 0 && 2 * numChild[v] >= numChild[u]) {
			depth[v] = depth[u];
			header[v] = header[u];
		} else {
			depth[v] = depth[u] + 1;
			header[v] = v;
		}

		HLD(v);
	}
}

int itMin[4 * MAX], ind[MAX], pos[MAX];

void build(int idx, int l, int r) {
	itMin[idx] = -1;
	if(l == r) {
		pos[l] = idx;
	} else {
		int mid = l + r >> 1;

		build(idx << 1, l, mid);
		build(idx << 1 | 1, mid + 1, r);
	}
}

void updateMin(int u, int val) {
	u = pos[u];
	itMin[u] = val;
	while(u > 1) {
		u >>= 1;
		itMin[u] = min(itMin[u << 1], itMin[u << 1 | 1]);
	}
} 

int getMin(int idx, int l, int r, int u, int v) {
	if(l > v || r < u) return INT_MAX;
	if(l >= u && r <= v) return itMin[idx];

	int mid = l + r >> 1;

	return min(getMin(idx << 1, l, mid, u, v), getMin(idx << 1 | 1, mid + 1, r, u, v));
}

int find_pos_min(int idx, int l, int r, int u, int v) {
	if(l > v || r < u || itMin[idx] > -1) return -1;
	if(l == r) return l;

	int mid = l + r >> 1;

	int x = find_pos_min(idx << 1, l, mid, u, v);
	if(x != -1) return x;
	return find_pos_min(idx << 1 | 1, mid + 1, r, u, v);
}

void get_path(int l, int r, vector <int> &res) {
	while(getMin(1, 1, N, l, r) == -1) {
		int x = find_pos_min(1, 1, N, l, r);
		res.push_back(ind[x]);
		updateMin(x, 0);
	}
}

vector <int> get_path(int u, int v) {
	vector <int> ans;
	if(depth[u] < depth[v]) swap(u, v);
	while(depth[u] > depth[v]) {
		get_path(local[header[u]], local[u], ans);
		u = par[header[u]];
	}

	while(header[u] != header[v]) {
		get_path(local[header[u]], local[u], ans);
		get_path(local[header[v]], local[v], ans);
		u = par[header[u]], v = par[header[v]];
	}
	if(local[u] > local[v]) swap(u, v);
	get_path(local[u] + 1, local[v], ans);
	return ans;
}

void you_make_it(void) {
	cin >> N >> M;
	edges.resize(M + 1);
	for (int i = 1; i <= M; ++i) {
		cin >> edges[i].fi >> edges[i].se;
	}
	for (int i = 1; i < N; ++i) {
		int x; cin >> x;
		auto [u, v] = edges[x];
		adj[u].push_back(v);
		adj[v].push_back(u);
		mst.push_back(x);
	}
	fill(ans + 1, ans + M + 1, -1);

	dfs(1, 0);
	depth[1] = header[1] = 1;
	HLD(1);
	for (int x : mst) {
		auto &[u, v] = edges[x];
		if(v == par[u]) swap(u, v);
		ind[local[v]] = x;
	}
	build(1, 1, N);

	int cur = 1;

	for (int i = 1; i <= M; ++i) {
		if(ans[i] != -1) continue;
		auto [u, v] = edges[i];
		vector <int> res = get_path(u, v);
		sort(res.begin(), res.end());
		for (auto x : res) {
			ans[x] = cur++;
		}

		if(ans[i] == -1) {
			ans[i] = cur++;
		}
	}

	for (int i = 1; i <= M; ++i) cout << ans[i] << " \n"[i == M];
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("riggedroads");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

riggedroads.cpp: In function 'void build(int, int, int)':
riggedroads.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int mid = l + r >> 1;
      |             ~~^~~
riggedroads.cpp: In function 'int getMin(int, int, int, int, int)':
riggedroads.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |  int mid = l + r >> 1;
      |            ~~^~~
riggedroads.cpp: In function 'int find_pos_min(int, int, int, int, int)':
riggedroads.cpp:88:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int mid = l + r >> 1;
      |            ~~^~~
riggedroads.cpp: In function 'int main()':
riggedroads.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:171:5: note: in expansion of macro 'file'
  171 |     file("riggedroads");
      |     ^~~~
riggedroads.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:171:5: note: in expansion of macro 'file'
  171 |     file("riggedroads");
      |     ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 24132 KB Output is correct
2 Correct 143 ms 26692 KB Output is correct
3 Correct 146 ms 23932 KB Output is correct
4 Correct 265 ms 36148 KB Output is correct
5 Correct 266 ms 36912 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 33148 KB Output is correct
2 Correct 69 ms 24780 KB Output is correct
3 Correct 36 ms 21840 KB Output is correct
4 Correct 76 ms 29356 KB Output is correct
5 Correct 29 ms 23120 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 44296 KB Output is correct
2 Correct 263 ms 50204 KB Output is correct
3 Correct 61 ms 27500 KB Output is correct
4 Correct 94 ms 31432 KB Output is correct
5 Correct 299 ms 49176 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 38780 KB Output is correct
2 Correct 109 ms 31696 KB Output is correct
3 Correct 357 ms 44740 KB Output is correct
4 Correct 325 ms 42296 KB Output is correct
5 Correct 27 ms 20312 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 3 ms 18780 KB Output is correct
9 Correct 87 ms 24132 KB Output is correct
10 Correct 143 ms 26692 KB Output is correct
11 Correct 146 ms 23932 KB Output is correct
12 Correct 265 ms 36148 KB Output is correct
13 Correct 266 ms 36912 KB Output is correct
14 Correct 107 ms 33148 KB Output is correct
15 Correct 69 ms 24780 KB Output is correct
16 Correct 36 ms 21840 KB Output is correct
17 Correct 76 ms 29356 KB Output is correct
18 Correct 29 ms 23120 KB Output is correct
19 Correct 235 ms 44296 KB Output is correct
20 Correct 263 ms 50204 KB Output is correct
21 Correct 61 ms 27500 KB Output is correct
22 Correct 94 ms 31432 KB Output is correct
23 Correct 299 ms 49176 KB Output is correct
24 Correct 164 ms 38780 KB Output is correct
25 Correct 109 ms 31696 KB Output is correct
26 Correct 357 ms 44740 KB Output is correct
27 Correct 325 ms 42296 KB Output is correct
28 Correct 27 ms 20312 KB Output is correct
29 Correct 318 ms 43208 KB Output is correct
30 Correct 344 ms 40960 KB Output is correct
31 Correct 363 ms 38336 KB Output is correct
32 Correct 140 ms 24660 KB Output is correct
33 Correct 348 ms 38668 KB Output is correct