oj.uz

Submission #333123

# Submission time Handle Problem Language Result Execution time Memory
333123 2020-12-04T16:47:06 Z guka415 Rigged Roads (NOI19_riggedroads) C++14
39 / 100
 769 ms 262148 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];
lca* tre;
set<int> toAdd;


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;
	vector<vector<int>> adja(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);
	}
	tre = new lca(adja);
}

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) {
	toAdd.clear();
	int f = tre->query(le, ri);
	ft[le] = { {goUp(le,f),0},-1 };
	ft[ri] = { {goUp(ri,f),0},-1 };
}

int main() {
	fast;
	input();
	dfsf(0, -1);
	vector<int> ret(m);
	int crt = 1;
	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);
			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 9 ms 12268 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 67172 KB Output is correct
2 Correct 207 ms 84704 KB Output is correct
3 Correct 134 ms 30460 KB Output is correct
4 Correct 340 ms 173264 KB Output is correct
5 Correct 351 ms 180560 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 311 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 161156 KB Output is correct
2 Correct 669 ms 177116 KB Output is correct
3 Correct 163 ms 57704 KB Output is correct
4 Correct 253 ms 80964 KB Output is correct
5 Correct 766 ms 200912 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 110776 KB Output is correct
2 Correct 282 ms 78696 KB Output is correct
3 Correct 769 ms 178252 KB Output is correct
4 Correct 726 ms 163312 KB Output is correct
5 Correct 50 ms 26088 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct
3 Correct 9 ms 12140 KB Output is correct
4 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -