Submission #877190

#	Time	Username	Problem	Language	Result	Execution time	Memory
877190		fanwen	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	363 ms	50204 KiB

riggedroads

#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 (stderr)

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 / 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