oj.uz

Submission #500649

# Submission time Handle Problem Language Result Execution time Memory
500649 2021-12-31T16:50:18 Z pooty Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 1428 ms 96080 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 448 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 26996 KB Output is correct
2 Correct 615 ms 43224 KB Output is correct
3 Correct 981 ms 42692 KB Output is correct
4 Correct 697 ms 71320 KB Output is correct
5 Correct 803 ms 75364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 44488 KB Output is correct
2 Correct 321 ms 27288 KB Output is correct
3 Correct 182 ms 14260 KB Output is correct
4 Correct 288 ms 34508 KB Output is correct
5 Correct 92 ms 12980 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 79468 KB Output is correct
2 Correct 636 ms 91984 KB Output is correct
3 Correct 130 ms 26636 KB Output is correct
4 Correct 242 ms 36948 KB Output is correct
5 Correct 714 ms 96080 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 53064 KB Output is correct
2 Correct 330 ms 35616 KB Output is correct
3 Correct 931 ms 77972 KB Output is correct
4 Correct 883 ms 72580 KB Output is correct
5 Correct 40 ms 7492 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 448 KB Output is correct
9 Correct 199 ms 26996 KB Output is correct
10 Correct 615 ms 43224 KB Output is correct
11 Correct 981 ms 42692 KB Output is correct
12 Correct 697 ms 71320 KB Output is correct
13 Correct 803 ms 75364 KB Output is correct
14 Correct 463 ms 44488 KB Output is correct
15 Correct 321 ms 27288 KB Output is correct
16 Correct 182 ms 14260 KB Output is correct
17 Correct 288 ms 34508 KB Output is correct
18 Correct 92 ms 12980 KB Output is correct
19 Correct 549 ms 79468 KB Output is correct
20 Correct 636 ms 91984 KB Output is correct
21 Correct 130 ms 26636 KB Output is correct
22 Correct 242 ms 36948 KB Output is correct
23 Correct 714 ms 96080 KB Output is correct
24 Correct 598 ms 53064 KB Output is correct
25 Correct 330 ms 35616 KB Output is correct
26 Correct 931 ms 77972 KB Output is correct
27 Correct 883 ms 72580 KB Output is correct
28 Correct 40 ms 7492 KB Output is correct
29 Correct 1428 ms 83296 KB Output is correct
30 Correct 1323 ms 85728 KB Output is correct
31 Correct 1148 ms 79460 KB Output is correct
32 Correct 840 ms 43096 KB Output is correct
33 Correct 1014 ms 78712 KB Output is correct