oj.uz

Submission #500629

# Submission time Handle Problem Language Result Execution time Memory
500629 2021-12-31T15:44:44 Z pooty Rigged Roads (NOI19_riggedroads) C++17
58 / 100
 2000 ms 101100 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];
			int edgeno = edgemap[{u, pr}];
			if (ans[edgeno] == -1) {
				edges.insert(edgeno);
			}
			u = pr;
		}
		while (v != anc) {
			int pr = parr[v];
			int edgeno = edgemap[{v, pr}];
			if (ans[edgeno] == -1) {
				edges.insert(edgeno);
			}
			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 204 KB Output is correct
2 Correct 1 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 204 KB Output is correct
2 Correct 1 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 7 ms 552 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 27712 KB Output is correct
2 Correct 515 ms 45132 KB Output is correct
3 Correct 892 ms 44832 KB Output is correct
4 Correct 657 ms 74936 KB Output is correct
5 Correct 738 ms 78936 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 45248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 83616 KB Output is correct
2 Correct 621 ms 96384 KB Output is correct
3 Correct 126 ms 27228 KB Output is correct
4 Correct 222 ms 38260 KB Output is correct
5 Correct 695 ms 101100 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 55304 KB Output is correct
2 Correct 260 ms 36804 KB Output is correct
3 Correct 877 ms 82516 KB Output is correct
4 Correct 834 ms 76688 KB Output is correct
5 Correct 38 ms 7540 KB Output is correct

Subtask #7
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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 7 ms 552 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 199 ms 27712 KB Output is correct
10 Correct 515 ms 45132 KB Output is correct
11 Correct 892 ms 44832 KB Output is correct
12 Correct 657 ms 74936 KB Output is correct
13 Correct 738 ms 78936 KB Output is correct
14 Execution timed out 2091 ms 45248 KB Time limit exceeded
15 Halted 0 ms 0 KB -