oj.uz

Submission #500632

# Submission time Handle Problem Language Result Execution time Memory
500632 2021-12-31T15:51:28 Z pooty Rigged Roads (NOI19_riggedroads) C++17
39 / 100
 845 ms 95304 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) {
					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) {
					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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Incorrect 1 ms 588 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 26360 KB Output is correct
2 Correct 477 ms 42488 KB Output is correct
3 Correct 832 ms 41876 KB Output is correct
4 Correct 634 ms 70580 KB Output is correct
5 Correct 702 ms 74548 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 43776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 78896 KB Output is correct
2 Correct 596 ms 91372 KB Output is correct
3 Correct 120 ms 25980 KB Output is correct
4 Correct 189 ms 36228 KB Output is correct
5 Correct 670 ms 95304 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 52448 KB Output is correct
2 Correct 250 ms 34884 KB Output is correct
3 Correct 845 ms 77612 KB Output is correct
4 Correct 832 ms 72108 KB Output is correct
5 Correct 37 ms 7040 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Incorrect 1 ms 588 KB Output isn't correct
7 Halted 0 ms 0 KB -