Submission #500649

#	Time	Username	Problem	Language	Result	Execution time	Memory
500649		pooty	Rigged Roads (NOI19_riggedroads)	C++17	100 / 100	1428 ms	96080 KiB

riggedroads

#define REP(i, n) for(int i = 0; i < n; i ++)
#define REPL(i,m, n) for(int i = m; i < n; i ++)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define M_PI 3.1415926535897932384
#define INF 999999999
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

void dfs(int u, vvi &adj, vi &parr, vi &harr, int curh) {
	harr[u] = curh;
	for (auto v: adj[u]) {
		if (parr[u] == v) continue;
		parr[v] = u;
		dfs(v, adj, parr, harr, curh+1);
	}
} 
int LCA(vi &parr, vi &harr, int u, int v) {
	if (u==v) return u;
	if (harr[u] < harr[v]) {
		return LCA(parr, harr, u,parr[v]);
	} else {
		return LCA(parr, harr, parr[u], v);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n,e;cin>>n>>e;
	vii edgearr(e);
	map<ii, int> edgemap;
	REP(i, e) {
		int u,v;cin>>u>>v;u--;v--;
		edgearr[i] = {u,v};
		edgemap[{u,v}] = i;
		edgemap[{v,u}] = i;
	}
	set<int> st;
	vvi adj(n);
	REP(i, n-1) {
		int k;cin>>k;k--;
		st.insert(k);
		auto [u,v] = edgearr[k];
		adj[u].push_back(v);
		adj[v].push_back(u);
	} 
	vi harr(n);
	vi parr(n,-1);
	dfs(0, adj,parr,harr,0);
	/*REP(i, n) {
		cout<<parr[i]<<" ";
	}
	cout<<"\n";
	REP(i, n) {
		cout<<harr[i]<<" ";
	}cout<<"..\n";*/
	vi ans(e, -1);
	int curlw = 1;
	REP(i, e) {
		if (ans[i] != -1) continue;
		if (st.find(i) != st.end()) {
			ans[i] = curlw++;
			continue;
		} 
		auto [u,v] = edgearr[i];
		int anc = LCA(parr, harr, u,v);
		set<int> edges;
		while (u!= anc) {
			int pr = parr[u];
			auto it = edgemap.find({u,pr});
			if (it != edgemap.end()) {
				int edgeno = it->second;
				if (ans[edgeno] == -1) {
					if (st.find(edgeno) != st.end()) {
						edges.insert(edgeno);
					}
				}
			}
			parr[u] = anc;
			u = pr;
		}
		while (v != anc) {
			int pr = parr[v];
			auto it = edgemap.find({v,pr});
			if (it != edgemap.end()) {
				int edgeno = it->second;
				if (ans[edgeno] == -1) {
					if (st.find(edgeno) != st.end()) {
						edges.insert(edgeno);
					}
				}
			}
			parr[v] = anc;
			v = pr;
		}
		for (auto kk: edges) {
			ans[kk] = curlw++;
		}
		ans[i] = curlw++;
	}
	REP(i, e) {
		cout<<ans[i]<<" ";
	}
}

• 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