Submission #333133

#	Time	Username	Problem	Language	Result	Execution time	Memory
333133		guka415	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	789 ms	201036 KiB

riggedroads

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <bitset>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<class T>
struct rmq {
	vector<vector<T>> a;
	vector<int> logs;
	int dep, len;
	rmq(vector<T> arr) {
		len = arr.size();
		dep = 0;
		int tmp = len;
		while (tmp) {
			tmp >>= 1;
			dep++;
		}
		a.resize(dep);
		foru(i, 0, dep) {
			a[i].resize(len);
			for (int j = 0; j + (1 << i) <= len; j++) {
				if (!i)a[i][j] = arr[j];
				else a[i][j] = min(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
			}
		}
		initLogs();
	}
	void initLogs() {
		logs.resize(len + 1);
		logs[1] = 0;
		foru(i, 2, len + 1)logs[i] = logs[i >> 1] + 1;
	}
	T query(int l, int r) {
		int mylen = logs[r - l + 1];
		return min(a[mylen][l], a[mylen][r - (1 << mylen) + 1]);
	}
};
struct lca {
	vector<vector<int>> adj;
	vector<int> appear;
	vector<pii> dep;
	rmq<pii>* tree;
	int sz;
	lca(vector<vector<int>> adjacency) {
		adj = adjacency;
		sz = adjacency.size();
		appear.resize(sz);
		dfsscan(0, -1, 0);
		tree = new rmq<pii>(dep);
	}
	void dfsscan(int src, int prev, int currdep) {
		appear[src] = dep.size();
		dep.pb(mp(currdep, src));
		for (auto x : adj[src]) {
			if (x == prev)continue;
			dfsscan(x, src, currdep + 1);
			dep.pb(mp(currdep, src));
		}
	}
	int query(int a, int b) {
		int x = min(appear[a], appear[b]), y = max(appear[a], appear[b]);
		return tree->query(x, y).second;
	}
};


const int sz = 5e5 + 5;
vector<pii> adj[sz];
vector<pii> e;
bitset<sz> good, done;
int n, m;
pair<pii, int> ft[sz];
int dep[sz];
set<int> toAdd;
vector<vector<int>> adja;


void dfsf(int src, int prv) {
	if (prv != -1) dep[src] = dep[prv] + 1;
	for (pii x : adj[src]) {
		if (x.first != prv) {
			ft[x.first] = { {src,1},x.second };
			dfsf(x.first, src);
		}
	}
}



void input() {
	cin >> n >> m;
	adja.resize(n);
	foru(i, 0, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		e.pb({ a,b });
	}
	foru(i, 0, n - 1) {
		int pos;
		cin >> pos; pos--;
		int a = e[pos].first, b = e[pos].second;
		good[pos] = 1;
		adj[a].pb({ b,pos });
		adj[b].pb({ a,pos });
		adja[a].pb(b);
		adja[b].pb(a);
	}
}

int goUp(int src, int upto) {
	if (dep[src] <= dep[upto])return src;
	else {
		if (ft[src].first.second && !done[ft[src].second])toAdd.insert(ft[src].second);
		int ret = goUp(ft[src].first.first, upto);
		ft[src] = { { ret,0 },-1 };
		return ret;
	}
}

void calcToAdd(int le, int ri, int f) {
	toAdd.clear();
	goUp(le, f);
	goUp(ri, f);
}

int main() {
	fast;
	input();
	dfsf(0, -1);
	vector<int> ret(m);
	int crt = 1;
	lca tre(adja);
	foru(i, 0, m) {
		if (done[i])continue;
		else if (good[i]) {
			ret[i] = crt++; done[i] = 1;
		}
		else {
			int l = e[i].first, r = e[i].second;
			calcToAdd(l, r, tre.query(l, r));
			for (int r : toAdd) {
				ret[r] = crt++;
				done[r] = 1;
			}
			ret[i] = crt++;
			done[i] = 1;
		}
	}
	foru(i, 0, m)cout << ret[i] << ' ';
	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