#include <bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
#define endl ("\n")
typedef long long ll;
using namespace std;
int n;
vector<vector<int>> g, dede;
vector<int> d, p;
struct DSU{
int n;
vector<int> ata, p;
DSU(int n, vector<int> p) : n(n), ata(n), p(p) {
for(int i = 0; i < n; i++) ata[i] = i;
}
void rem(int a){
int par = find(p[a]);
ata[a] = par;
}
int find(int a){
if(a == -1) return -1;
if(ata[a] == a) return a;
return ata[a] = find(ata[a]);
}
};
void dfs1(int u, int ata = -1){
for(int go : g[u]){
if(go == ata) continue;
p[go] = u;
d[go] = d[u] + 1;
dfs1(go, u);
}
}
const int logar = 32;
void build_lca(){
dede.resize(n, vector<int>(logar));
for(int i = 0; i < n; i++){
dede[i][0] = p[i];
}
for(int k = 1; k < logar; k++){
for(int i = 0; i < n; i++){
if(dede[i][k - 1] == -1)
dede[i][k] = -1;
else
dede[i][k] = dede[dede[i][k - 1]][k - 1];
}
}
}
int find_lca(int a, int b){
if(d[a] < d[b]) swap(a, b);
for(int k = logar - 1; k >= 0; k--){
if((1<<k) & (d[a] - d[b])){
a = dede[a][k];
}
}
for(int k = logar - 1; k >= 0; k--){
if(dede[a][k] != dede[b][k])
a = dede[a][k], b = dede[b][k];
}
if(a == b) return a;
return p[a];
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int m;
cin >> n;
g.resize(n);
for(int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
a--, b--;
g[a].pb(b);
g[b].pb(a);
}
d.resize(n), p.resize(n);
dfs1(0);
p[0] = -1;
cin >> m;
vector<array<int, 3>> MIN, MAX;
for(int i = 0; i < m; i++){
char c;
cin >> c;
int x, y, z;
cin >> x >> y >> z;
x--, y--;
if(c == 'm')
MIN.pb({z, x, y});
else
MAX.pb({z, x, y});
}
build_lca();
sort(all(MIN));
reverse(all(MIN));
sort(all(MAX));
DSU max_free(n, p), min_free(n, p);
vector<int> max_val, min_val;
vector<int> max_assigned(n, -1), min_assigned(n, -1);
vector<set<int>> max_can_go, min_can_go;
int c = 0;
for(auto [z, x, y] : MAX){
int lca = find_lca(x, y);
max_val.pb(z);
max_can_go.emplace_back();
while(1){
x = max_free.find(x);
if(x == -1 || d[x] <= d[lca]) break;
max_can_go[c].insert(x);
max_free.rem(x);
max_assigned[x] = c;
}
while(1){
y = max_free.find(y);
if(y == -1 || d[y] <= d[lca]) break;
max_can_go[c].insert(y);
max_free.rem(y);
max_assigned[y] = c;
}
c++;
}
c = 0;
for(auto [z, x, y] : MIN){
int lca = find_lca(x, y);
min_val.pb(z);
min_can_go.emplace_back();
while(1){
x = min_free.find(x);
if(x == -1 || d[x] <= d[lca]) break;
min_can_go[c].insert(x);
min_free.rem(x);
min_assigned[x] = c;
}
while(1){
y = min_free.find(y);
if(y == -1 || d[y] <= d[lca]) break;
min_can_go[c].insert(y);
min_free.rem(y);
min_assigned[y] = c;
}
c++;
}
vector<int> ans(n);
vector<bool> answered(n);
set<pair<int, int>> max_sets, min_sets;
for(int i = 0; i < (int) max_can_go.size(); i++)
max_sets.insert({max_can_go[i].size(), i});
for(int i = 0; i < (int) min_can_go.size(); i++)
min_sets.insert({min_can_go[i].size(), i});
while(!max_sets.empty() || !min_sets.empty()){
bool good = 0;
while(!max_sets.empty() && max_sets.begin()->first == 1){
c = max_sets.begin()->second;
auto it = max_can_go[c].begin();
answered[*it] = 1;
ans[*it] = max_val[c];
int ind = min_assigned[*it];
if(ind != -1){
min_sets.erase({min_can_go[ind].size(), ind});
min_can_go[ind].erase(*it);
min_sets.insert({min_can_go[ind].size(), ind});
}
max_sets.erase(max_sets.begin());
good = 1;
}
while(!min_sets.empty() && min_sets.begin()->first == 1){
c = min_sets.begin()->second;
auto it = min_can_go[c].begin();
answered[*it] = 1;
ans[*it] = min_val[c];
int ind = max_assigned[*it];
if(ind != -1){
max_sets.erase({max_can_go[ind].size(), ind});
max_can_go[ind].erase(*it);
max_sets.insert({max_can_go[ind].size(), ind});
}
min_sets.erase(min_sets.begin());
good = 1;
}
if(!good && !max_sets.empty()){
c = max_sets.begin()->second;
auto it = max_can_go[c].begin();
answered[*it] = 1;
ans[*it] = max_val[c];
int ind = min_assigned[*it];
if(ind != -1){
min_sets.erase({min_can_go[ind].size(), ind});
min_can_go[ind].erase(*it);
min_sets.insert({min_can_go[ind].size(), ind});
}
max_sets.erase(max_sets.begin());
good = 1;
}
if(!min_sets.empty() && !good){
c = min_sets.begin()->second;
auto it = min_can_go[c].begin();
answered[*it] = 1;
ans[*it] = min_val[c];
int ind = max_assigned[*it];
if(ind != -1){
max_sets.erase({max_can_go[ind].size(), ind});
max_can_go[ind].erase(*it);
max_sets.insert({min_can_go[ind].size(), ind});
}
min_sets.erase(min_sets.begin());
good = 1;
}
if((!max_sets.empty() || !min_sets.empty()) && !good)
assert(0);
}
for(int i = 1; i < n; i++){
cout << i + 1 << ' ' << p[i] + 1 << ' ';
if(answered[i])
cout << ans[i] << endl;
else if(max_assigned[i] != -1){
cout << max_val[max_assigned[i]] << endl;
}
else if(min_assigned[i] != -1){
cout << min_val[min_assigned[i]] << endl;
}
else cout << 0 << endl;
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:109:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
109 | for(auto [z, x, y] : MAX){
| ^
minmaxtree.cpp:131:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | for(auto [z, x, y] : MIN){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1034 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
32700 KB |
Output is correct |
| 2 |
Correct |
108 ms |
31476 KB |
Output is correct |
| 3 |
Correct |
106 ms |
30152 KB |
Output is correct |
| 4 |
Correct |
108 ms |
33096 KB |
Output is correct |
| 5 |
Correct |
100 ms |
30144 KB |
Output is correct |
| 6 |
Correct |
111 ms |
32704 KB |
Output is correct |
| 7 |
Correct |
106 ms |
30524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1016 ms |
22912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1034 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
