oj.uz

Submission #708199

# Submission time Handle Problem Language Result Execution time Memory
708199 2023-03-11T09:41:03 Z dsyz Rigged Roads (NOI19_riggedroads) C++17
100 / 100
 349 ms 55396 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (300005)
ll N,E;
vector<pair<ll,ll> > v[MAXN]; //b, index
pair<ll,ll> edges[MAXN];
ll R[MAXN];
ll parent[MAXN];
ll par[MAXN];
ll depth[MAXN];
ll find_set(ll x){
	if(parent[x] == x) return x;
	parent[x] = find_set(parent[x]);
	return parent[x];
}
bool same_set(ll x,ll y){
	return find_set(x) == find_set(y);
}
void merge_set(ll x,ll y){
	x = find_set(x);
	y = find_set(y);
	if(depth[x] < depth[y]){
		swap(x,y);
	}
	parent[x] = y;
}
void dfs(ll x,ll p){
	for(auto u : v[x]){
		if(u.first != p){
			depth[u.first] = depth[x] + 1;
			par[u.first] = x;
			dfs(u.first,x);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>E;
	for(ll i = 0;i < E;i++){
		cin>>edges[i].first>>edges[i].second;
		edges[i].first--;
		edges[i].second--;	
	}
	ll R[N - 1];
	bool inR[E];
	memset(inR,0,sizeof(inR));
	for(ll i = 0;i < N - 1;i++){
		cin>>R[i];
		R[i]--;
		inR[R[i]] = 1;
		ll a = edges[R[i]].first;
		ll b = edges[R[i]].second;
		v[a].push_back({b,R[i]});
		v[b].push_back({a,R[i]});
	}
	for(ll i = 0;i < N;i++){
		parent[i] = i;
	}
	par[0] = -1;
	dfs(0,-1);
	ll upedgeindex[N]; //edge index between node parent[i] and node i
	memset(upedgeindex,-1,sizeof(upedgeindex));
	for(ll i = 0;i < N;i++){
		for(auto u : v[i]){
			if(depth[u.first] < depth[i]){
				upedgeindex[i] = u.second;
				break;
			}
		}
	}
	ll curweight = 1;
	ll ans[E];
	memset(ans,-1,sizeof(ans));
	for(ll i = 0;i < E;i++){ //list of edges
		if(ans[i] != -1){
			continue;
		}
		if(inR[i]){
			ans[i] = curweight;
			curweight++;
			merge_set(edges[i].first,edges[i].second);
		}else{
			ll a = find_set(edges[i].first);
			ll b = find_set(edges[i].second);
			vector<ll> wait;
			//UFDS jumping on tree (different from binary jumping)
			while(a != b){
				//this will stop when a and b meet at their LCA
				//or above if the above is also merged
				//but as long as they meet, it also works
				if(depth[a] > depth[b]){
					wait.push_back(upedgeindex[a]);
					merge_set(a,par[a]);
					a = find_set(a);
				}else{ 
					//Note that jumping must continue even at same depth as they may not be at same node
					wait.push_back(upedgeindex[b]);
					merge_set(b,par[b]);
					b = find_set(b);
				}
			}
			sort(wait.begin(),wait.end());
			for(auto index : wait){
				ans[index] = curweight;
				curweight++;
			}
			ans[i] = curweight;
			curweight++;
			wait.clear();
		}
	}
	for(ll i = 0;i < E;i++){
		cout<<ans[i]<<" ";
	}
	cout<<'\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7512 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 20316 KB Output is correct
2 Correct 79 ms 26848 KB Output is correct
3 Correct 83 ms 20612 KB Output is correct
4 Correct 135 ms 43296 KB Output is correct
5 Correct 141 ms 45220 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 27980 KB Output is correct
2 Correct 44 ms 16848 KB Output is correct
3 Correct 24 ms 12244 KB Output is correct
4 Correct 53 ms 22508 KB Output is correct
5 Correct 22 ms 13500 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 47076 KB Output is correct
2 Correct 239 ms 53176 KB Output is correct
3 Correct 55 ms 20320 KB Output is correct
4 Correct 91 ms 26592 KB Output is correct
5 Correct 292 ms 55396 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 34808 KB Output is correct
2 Correct 116 ms 26464 KB Output is correct
3 Correct 299 ms 49416 KB Output is correct
4 Correct 289 ms 45888 KB Output is correct
5 Correct 20 ms 10972 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7512 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 45 ms 20316 KB Output is correct
10 Correct 79 ms 26848 KB Output is correct
11 Correct 83 ms 20612 KB Output is correct
12 Correct 135 ms 43296 KB Output is correct
13 Correct 141 ms 45220 KB Output is correct
14 Correct 82 ms 27980 KB Output is correct
15 Correct 44 ms 16848 KB Output is correct
16 Correct 24 ms 12244 KB Output is correct
17 Correct 53 ms 22508 KB Output is correct
18 Correct 22 ms 13500 KB Output is correct
19 Correct 246 ms 47076 KB Output is correct
20 Correct 239 ms 53176 KB Output is correct
21 Correct 55 ms 20320 KB Output is correct
22 Correct 91 ms 26592 KB Output is correct
23 Correct 292 ms 55396 KB Output is correct
24 Correct 159 ms 34808 KB Output is correct
25 Correct 116 ms 26464 KB Output is correct
26 Correct 299 ms 49416 KB Output is correct
27 Correct 289 ms 45888 KB Output is correct
28 Correct 20 ms 10972 KB Output is correct
29 Correct 349 ms 45872 KB Output is correct
30 Correct 296 ms 46060 KB Output is correct
31 Correct 307 ms 45880 KB Output is correct
32 Correct 75 ms 19880 KB Output is correct
33 Correct 299 ms 45440 KB Output is correct