Last active
January 9, 2022 11:34
-
-
Save shadmansaleh/9e7e7099f8aa7ddc93da95d509d1c886 to your computer and use it in GitHub Desktop.
Possible solution to https://codeforces.com/problemset/problem/1620/E?mobile
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
inline int *new_query(int op, int x, int y); | |
inline void clear_queries(int **queries, int cnt); | |
int **get_queries(int cnt); | |
inline int get_replaced_val(unordered_map<int, int> &ref, int query); | |
int main() { | |
ios_base::sync_with_stdio(false); | |
cin.tie(NULL); | |
cout.tie(NULL); | |
int cnt{}; | |
cin >> cnt; | |
int **queries = get_queries(cnt); | |
int *query = nullptr; | |
unordered_map<int, int> replace_ref{}; | |
vector<int> result{}; | |
for (int i = cnt - 1; i >= 0; --i) { | |
query = queries[i]; | |
if (query[0] == 1) { | |
result.push_back(get_replaced_val(replace_ref, query[1])); | |
} else { | |
replace_ref[query[1]] = query[2]; | |
} | |
} | |
for (int i = result.size() - 1; i >= 0; --i) | |
cout << result[i] << ' '; | |
clear_queries(queries, cnt); | |
return 0; | |
} | |
inline int *new_query(int op, int x, int y = 0) { | |
int *query = new int[3]; | |
query[0] = op; | |
query[1] = x; | |
query[2] = y; | |
return query; | |
} | |
inline void clear_queries(int **queries, int cnt) { | |
for (int i = 0; i < cnt; ++i) | |
delete queries[i]; | |
delete[] queries; | |
} | |
int **get_queries(int cnt) { | |
int **queries = new int *[cnt]; | |
int op, x, y; | |
for (int i = 0; i < cnt; ++i) { | |
cin >> op >> x; | |
if (op == 1) { | |
queries[i] = new_query(op, x); | |
} else { | |
cin >> y; | |
queries[i] = new_query(op, x, y); | |
} | |
} | |
return queries; | |
} | |
inline int get_replaced_val(unordered_map<int, int> &ref, int query) { | |
try { | |
while (ref[query] && ref[query] != query) | |
query = ref[query]; | |
} catch(exception &e) { | |
return query; | |
} | |
return query; | |
} | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
inline int *new_query(int op, int x, int y); | |
inline void clear_queries(int **queries, int cnt); | |
int **get_queries(int cnt); | |
int main() { | |
ios_base::sync_with_stdio(false); | |
cin.tie(NULL); | |
cout.tie(NULL); | |
int cnt{}; | |
cin >> cnt; | |
int **queries = get_queries(cnt); | |
int *query = nullptr; | |
int *replace_ref = new int[5000001]; | |
for (int i=0; i <= 500000; ++i) replace_ref[i] = i; | |
vector<int> result{}; | |
for (int i = cnt - 1; i >= 0; --i) { | |
query = queries[i]; | |
if (query[0] == 1) { | |
result.push_back(replace_ref[query[1]]); | |
} else { | |
replace_ref[query[1]] = replace_ref[query[2]]; | |
} | |
} | |
for (int i = result.size() - 1; i >= 0; --i) | |
cout << result[i] << ' '; | |
delete[] replace_ref; | |
clear_queries(queries, cnt); | |
return 0; | |
} | |
inline int *new_query(int op, int x, int y = 0) { | |
int *query = new int[3]; | |
query[0] = op; | |
query[1] = x; | |
query[2] = y; | |
return query; | |
} | |
inline void clear_queries(int **queries, int cnt) { | |
for (int i = 0; i < cnt; ++i) | |
delete[] queries[i]; | |
delete[] queries; | |
} | |
int **get_queries(int cnt) { | |
int **queries = new int *[cnt]; | |
int op, x, y; | |
for (int i = 0; i < cnt; ++i) { | |
cin >> op >> x; | |
if (op == 1) { | |
queries[i] = new_query(op, x); | |
} else { | |
cin >> y; | |
queries[i] = new_query(op, x, y); | |
} | |
} | |
return queries; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define MAX_SIZE 500000 | |
int find_val_id(int* ids, int ids_size, int val); | |
int main() { | |
int result[MAX_SIZE]; | |
int num_ids[MAX_SIZE]; | |
int result_end = -1; | |
int num_id_end = -1; | |
int operation_type = 0; | |
int append_num = 0, find_num = 0, replace_num = 0; | |
int current_id = -1, find_id = -1, replace_id = -1; | |
int query_num = 0; | |
scanf("%d", &query_num); | |
for (int i = 0; i < query_num; ++i) { | |
scanf("%d", &operation_type); | |
if (operation_type == 1) { | |
scanf("%d", &append_num); | |
if (result_end == -1 && num_id_end == -1) { | |
result_end = 0; | |
num_id_end = 0; | |
} | |
current_id = find_val_id(num_ids, num_id_end, append_num); | |
if (current_id == -1) { | |
num_ids[num_id_end++] = append_num; | |
current_id = num_id_end - 1; | |
} | |
result[result_end++] = current_id; | |
} else if (operation_type == 2) { | |
scanf("%d %d", &find_num, &replace_num); | |
find_id = find_val_id(num_ids, num_id_end, find_num);; | |
if (find_id != -1) { | |
replace_id = find_val_id(num_ids, num_id_end, replace_num); | |
if (replace_id == -1) { | |
num_ids[find_id] = replace_num; | |
} else { | |
for (int m = 0; m < result_end; ++m) { | |
if (result[m] == find_id) { | |
result[m] = replace_id; | |
} | |
} | |
} | |
} | |
} | |
} | |
for (int j = 0; j < result_end; ++j) { | |
printf("%d", num_ids[result[j]]); | |
if (j != result_end-1) { | |
putchar(' '); | |
} | |
} | |
return 0; | |
} | |
int find_val_id(int* ids, int ids_size, int val) { | |
for (int i = 0; i < ids_size; ++i) { | |
if (ids[i] == val) { | |
return i; | |
} | |
} | |
return -1; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
int main() { | |
int query_num{}; | |
std::cin >> query_num; | |
std::vector<int> result{}; | |
for (int i=0; i < query_num; i++) { | |
int operation_type{}; | |
std::cin >> operation_type; | |
if (operation_type == 1) { | |
int append{}; | |
std::cin >> append; | |
result.push_back(append); | |
} else { | |
int find_num{}, replace_num{}; | |
std::cin >> find_num >> replace_num; | |
for (auto &x: result) if (x == find_num) x = replace_num; | |
} | |
} | |
for (auto x: result) | |
std::cout << x << ' '; | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment