#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <fstream>
using namespace std;
template <typename T>
class normaliser{
map<T, int> forward;
map<int, T> backward;
int curr = 0;
public:
normaliser(){}
int size(){
return backward.size(); }
void add(T x){
backward[curr]= x;
forward[x] = curr;
++curr; }
int norm(T x){
return forward[x]; }
T denorm(int x){
return backward[x]; } };
class orienter{
int n;
vector<vector<int>> vec;
vector<int> ret;
vector<bool> viz;
int find_cyclic_node(int cur, int prev = -1){
viz[cur] = true;
for(auto next : vec[cur]){
if(next != prev){
if(viz[next])
return cur;
else{
auto ret = find_cyclic_node(next, cur);
if(ret != -1) return ret; } } }
return -1; }
void dfs(int cur, int prev){
for(auto next : vec[cur]){
if(next == prev) continue;
if(ret[next] == -1) ret[next] = cur;
dfs(next, cur); } }
public:
orienter(int N): n(N), vec(n), viz(n, -1), ret(n, -1){}
void add(int x, int y){
vec[x].push_back(y);
vec[y].push_back(x); }
vector<int> get_next(){
for(int i = 0; i < n; ++i){
if(viz[i]) continue;
auto tmp = find_cyclic_node(i);
dfs(tmp, -1); }
return ret; } };
class special_bipartite_matcher{
int n, m;
vector<vector<int>> vec, rvec;
public:
special_bipartite_matcher(int N, int M): n(N), m(M), vec(n), rvec(m){}
void add(int x, int y){
vec[x].push_back(y);
rvec[y].push_back(x); }
map<int, int> build_matching(){
map<int, int> ret;
{
queue<int> todo;
for(int i = 0; i < vec.size(); ++i)
if(vec[i].size() == 1)
todo.push(i);
while(!todo.empty()){
auto x = todo.front();
todo.pop();
auto y = vec[x][0];
ret[x] = y;
for(auto z : rvec[y]){
vec[z].erase(remove(begin(vec[z]), end(vec[z]), y), end(vec[z]));
if(vec[z].size() == 1) todo.push(z); }
rvec[y].clear();
}
orienter o(n);
for(int i = 0; i < n; ++i)
if(vec[i].size() == 2)
o.add(vec[i][0], vec[i][1]);
auto next = o.get_next();
for(int i = 0; i < n; ++i)
if(vec[i].size() == 2)
if(next[vec[i][0]] == vec[i][1])
ret[i] = vec[i][0];
return ret; } } };
set<int> build_set_xor(set<int> a, set<int> b){
if(a.size() < b.size())
swap(a, b);
for(auto x : b){
if(a.find(x) == end(a)) a.insert(x);
else a.erase(x); }
return a; }
class min_query_joiner{
int n;
vector<vector<int>> vec, restrictions;
map<pair<int, int>, int> final_restrictions;
set<int> dfs(int cur, int prev){
set<int> curr(begin(restrictions[cur]), end(restrictions[cur]));
for(auto next : vec[cur])
if(next != prev)
curr = build_set_xor(move(curr), dfs(next, cur));
if(!curr.empty())
final_restrictions[minmax(cur, prev)] = *begin(curr);
return curr; }
public:
min_query_joiner(int N): n(N), vec(n), restrictions(n){}
void add_edge(int x, int y){
vec[x].push_back(y);
vec[y].push_back(x); }
void add_restriction(int x, int y, int z){
restrictions[x].push_back(z);
restrictions[y].push_back(z); }
map<pair<int, int>, int> get_restrictions(){
dfs(1, 0);
return final_restrictions; } };
int main(){
int n;
cin >> n;
normaliser<pair<int, int>> from_edge;
min_query_joiner mqj(n+1);
min_query_joiner Mqj(n+1);
set<pair<int, int>> edges;
for(int i = 0, x, y; i < n-1; ++i){
cin >> x >> y;
from_edge.add(minmax(x, y));
edges.insert(minmax(x, y));
mqj.add_edge(x, y);
Mqj.add_edge(x, y); }
normaliser<int> from_weight;
int m;
cin >> m;
for(int i = 0, x, y, z; i < m; ++i){
char ch;
cin >> ws >> ch >> x >> y >> z;
from_weight.add(z);
(ch == 'm' ? mqj : Mqj).add_restriction(x, y, (ch == 'm' ? -z : z)); }
auto mrest = mqj.get_restrictions(),
Mrest = Mqj.get_restrictions();
special_bipartite_matcher bm(n-1, m);
for(auto x : edges){
if(mrest.find(x) != end(mrest)) bm.add(from_edge.norm(x), from_weight.norm(-mrest[x]));
if(Mrest.find(x) != end(Mrest)) bm.add(from_edge.norm(x), from_weight.norm(Mrest[x])); }
auto matching = bm.build_matching();
for(auto& x : edges)
if(matching.find(from_edge.norm(x)) != end(matching))
cout << x.first << ' ' << x.second << ' ' << from_weight.denorm(matching[from_edge.norm(x)]) << '\n';
else if(mrest.find(x) != end(mrest))
cout << x.first << ' ' << x.second << ' ' << -mrest[x] << '\n';
else if(Mrest.find(x) != end(Mrest))
cout << x.first << ' ' << x.second << ' ' << Mrest[x] << '\n';
else
cout << x.first << ' ' << x.second << ' ' << 123456 << '\n';
return 0; }
Compilation message
minmaxtree.cpp: In constructor 'orienter::orienter(int)':
minmaxtree.cpp:33:18: warning: 'orienter::viz' will be initialized after [-Wreorder]
vector<bool> viz;
^~~
minmaxtree.cpp:32:17: warning: 'std::vector<int> orienter::ret' [-Wreorder]
vector<int> ret;
^~~
minmaxtree.cpp:52:5: warning: when initialized here [-Wreorder]
orienter(int N): n(N), vec(n), viz(n, -1), ret(n, -1){}
^~~~~~~~
minmaxtree.cpp: In member function 'std::map<int, int> special_bipartite_matcher::build_matching()':
minmaxtree.cpp:75:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); ++i)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
60688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
980 ms |
60688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
