Submission #59739

#	Time	Username	Problem	Language	Result	Execution time	Memory
59739		model_code	Min-max tree (BOI18_minmaxtree)	C++17	0 / 100	1071 ms	60688 KiB

minmaxtree

#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 (stderr)

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)
                            ~~^~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42