Submission #1264242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264242		tminh	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	267 ms	62148 KiB

riggedroads

#include "bits/stdc++.h"
using namespace std;

#define task ""
#define ll long long
#define endl '\n'
#define u first
#define v second
#define vall(a) (a).begin(), (a).end()
#define sze(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>


#define ep emplace_back
#define pb push_back
#define pf push_front


const ll mod = 1e9 + 7;
const int N = 3e5 + 5;
const ll oo = 1e9;

bool START;
int n, m, s[N], a[N], ra[N];
pii e[N];
vector<pii> adj[N]; 

struct ST {
	pii st[N << 2];
	void update(int id, int l, int r, int i, int val) {
		if (l > i || r < i) return;
		if (l == r) {
			st[id] = make_pair(val, i);
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, i, val);
		update(id << 1 | 1, mid + 1, r, i, val);
		st[id] = min(st[id << 1], st[id << 1 | 1]);
	}
	pii get(int id, int l, int r, int u, int v) {
		if (l > v || r < u) return make_pair(oo, oo);
		if (l >= u && r <= v) return st[id];
		int mid = (l + r) >> 1;
		return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
	}
} st;


int id[N], ans[N];

int cur = 1;
vector<int> arr;
struct HLD {
	int chain[N], par[N], sz[N], nxt[N], h[N];
	void dfs(int u) {
		sz[u] = 1;
		nxt[u] = 0;
		for (auto [v, w] : adj[u]) {
			if (v == par[u]) continue;
			par[v] = u;
			a[v] = w;
			ra[w] = v;
			h[v] = h[u] + 1;
			dfs(v);
			if (sz[nxt[u]] < sz[v]) nxt[u] = v;
			sz[u] += sz[v];
		}
	}
	int idx = 1;
	void assign_chain(int u, int cur) {
		chain[u] = cur; id[u] = idx++;
		if (nxt[u]) assign_chain(nxt[u], cur);
		for (auto[v, w] : adj[u]) if (v != par[u] && v != nxt[u]) assign_chain(v, v);
	}
	void get(int u, int v) {
		for (; chain[u] != chain[v]; v = par[chain[v]]) {
			if (h[chain[u]] > h[chain[v]]) swap(u, v);
			while(true) {
				auto[val, idx] = st.get(1, 1, n, id[chain[v]], id[v]);
				if (val == oo) break;
				arr.pb(val);
				st.update(1, 1, n, idx, oo);
			}
		}
		if (h[u] > h[v]) swap(u, v);
		while(true) {
			auto[val, idx] = st.get(1, 1, n, id[u] + 1, id[v]);
			if (val == oo) break;
			arr.pb(val);
			st.update(1, 1, n, idx, oo);
		}
			
		sort(vall(arr));
		for (int x : arr) ans[x] = cur++;
		arr.clear();
	}
} hld;

bool check[N];
inline void solve() {
	hld.dfs(1);
	hld.assign_chain(1, 1);
	for (int i = 1; i <= n; ++i) st.update(1, 1, n, id[i], a[i]);
		
	for (int i = 1; i <= m; ++i) {
		if (ans[i]) continue;
		
		if (check[i]) {
			st.update(1, 1, n, id[ra[i]], oo);
			ans[i] = cur++;
			continue;
		}
		
		auto[u, v] = e[i];
		hld.get(u, v);
		ans[i] = cur++;
	}
	for (int i = 1; i <= m; ++i) cout << ans[i] << " ";
}


inline void input() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;
    for (int i = 1; i < n; ++i) {
    	cin >> s[i];
    	check[s[i]] = true;
    	auto[u, v] = e[s[i]];
    	adj[u].pb(make_pair(v, s[i]));
    	adj[v].pb(make_pair(u, s[i]));
    }
    return solve();
}
bool END;

int main() {
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    input();
    
    
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
    cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n";
    return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'int main()':
riggedroads.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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