oj.uz

Submission #333133

# Submission time Handle Problem Language Result Execution time Memory
333133 2020-12-04T17:36:14 Z guka415 Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 789 ms 201036 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 10 ms 12524 KB Output is correct
5 Correct 9 ms 12524 KB Output is correct
6 Correct 9 ms 12524 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 9 ms 12524 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 69088 KB Output is correct
2 Correct 200 ms 87396 KB Output is correct
3 Correct 126 ms 30940 KB Output is correct
4 Correct 333 ms 178636 KB Output is correct
5 Correct 349 ms 186192 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 81508 KB Output is correct
2 Correct 95 ms 36588 KB Output is correct
3 Correct 51 ms 24684 KB Output is correct
4 Correct 145 ms 63204 KB Output is correct
5 Correct 57 ms 32496 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 160992 KB Output is correct
2 Correct 591 ms 177248 KB Output is correct
3 Correct 152 ms 57976 KB Output is correct
4 Correct 228 ms 81140 KB Output is correct
5 Correct 672 ms 201036 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 111068 KB Output is correct
2 Correct 254 ms 79076 KB Output is correct
3 Correct 704 ms 178444 KB Output is correct
4 Correct 664 ms 163420 KB Output is correct
5 Correct 46 ms 26216 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 8 ms 12140 KB Output is correct
4 Correct 10 ms 12524 KB Output is correct
5 Correct 9 ms 12524 KB Output is correct
6 Correct 9 ms 12524 KB Output is correct
7 Correct 9 ms 12396 KB Output is correct
8 Correct 9 ms 12524 KB Output is correct
9 Correct 122 ms 69088 KB Output is correct
10 Correct 200 ms 87396 KB Output is correct
11 Correct 126 ms 30940 KB Output is correct
12 Correct 333 ms 178636 KB Output is correct
13 Correct 349 ms 186192 KB Output is correct
14 Correct 201 ms 81508 KB Output is correct
15 Correct 95 ms 36588 KB Output is correct
16 Correct 51 ms 24684 KB Output is correct
17 Correct 145 ms 63204 KB Output is correct
18 Correct 57 ms 32496 KB Output is correct
19 Correct 531 ms 160992 KB Output is correct
20 Correct 591 ms 177248 KB Output is correct
21 Correct 152 ms 57976 KB Output is correct
22 Correct 228 ms 81140 KB Output is correct
23 Correct 672 ms 201036 KB Output is correct
24 Correct 429 ms 111068 KB Output is correct
25 Correct 254 ms 79076 KB Output is correct
26 Correct 704 ms 178444 KB Output is correct
27 Correct 664 ms 163420 KB Output is correct
28 Correct 46 ms 26216 KB Output is correct
29 Correct 713 ms 155480 KB Output is correct
30 Correct 789 ms 169312 KB Output is correct
31 Correct 737 ms 177484 KB Output is correct
32 Correct 130 ms 30308 KB Output is correct
33 Correct 720 ms 178636 KB Output is correct