Submission #1273052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273052		goulthen	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	291 ms	73400 KiB

riggedroads

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

#define int long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

const int MAXN = 3e5+10;
const int INF = 1e18+10;
vector<int> g[MAXN];
int u[MAXN], v[MAXN], val[MAXN], dep[MAXN],a2[MAXN];
vector<int> a[MAXN];
int spa[MAXN];
bool ispa[MAXN];

set<int> dfs(int u, int p = -1) {	
	set<int> st;
	for(int &x : a[u]) st.insert(x);
	int mn = INF;
	
	for (int &v : g[u]) {
		if (v==p) continue;
		dep[v] = dep[u] + 1;
		set<int> c = dfs(v,u);
		if (st.size() < c.size()) swap(st,c);
		for (const int &x : c) {
			mn = min(x,mn);
			if (st.find(x) != st.end()) st.erase(x);
			else st.insert(x);
		}
	}

	if(st.size() > 0) mn = min(mn,*st.begin());
	a2[u] = mn;
	return st;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int n,m; cin >> n >> m;
	rep(i,1,m) cin >> u[i] >> v[i];
	
	rep(i,1,n-1) {
		int c;cin >> c;
		spa[i] = c;
		ispa[c] = 1;
		int x = u[c], y=v[c];
		g[x].pb(y);
		g[y].pb(x);
	}

	vector<array<int,3>> ord;
	rep(i,1,m) if (!ispa[i]) {
		a[u[i]].pb(i);
		a[v[i]].pb(i);
		ord.pb({i,1,i});
	}

	dfs(1);
	//rep(i,1,n) cout << a2[i] << '\n';


	rep(i,1,n-1) {
		int x = spa[i];
		ord.pb({min(x,max(a2[u[x]], a2[v[x]])), 0, x});
	}

	sort(ord.begin(),ord.end());

	rep(i,1,m) {
		val[ord[i-1][2]] = i;
	}


	rep(i,1,m) cout << val[i] << " \n"[i==m];
	return 0;
}

• 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