답안 #137648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137648	2019-07-28T08:14:36 Z	mechfrog88	Min-max tree (BOI18_minmaxtree)	C++14	컴파일 오류	0 ms	0 KB

minmaxtree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;

vector <ll> euler;
vector <ll> height;
vector <ll> index;
vector <ll> parent;
vector <vector<pair<ll,ll>>> st;
vector <vector<ll>> graph;
ll n;

void dfs(ll v = 1, ll p = 0,ll h = 1){
    euler.push_back(v);
    index[v] = euler.size()-1;
    parent[v] = p;
    height[v] = h;
    for (int z=0;z<graph[v].size();z++){
        if (graph[v][z] == p) continue;
        dfs(graph[v][z],v,h+1);
    }
    euler.push_back(v);
}

void build(){
    for (int z=0;z<n;z++){
        st[z][0].first = height[z];
        st[z][0].second = euler[z];
    }
    for (int x=1;x<=log2(n);x++){
        for (int z=0;z + (1 << (x-1))<n;z++){
            if (st[z][x-1].first < st[z + (1 << (x-1))][x-1].first){
                st[z][x].second = st[z][x-1].second;
            } else {
                st[z][x].second = st[z + (1 << (x-1))][x-1].second;
            }
            st[z][x].first = min(st[z][x-1].first,st[z + (1 << (x-1))][x-1].first);
        }
    }
}

ll lca(ll x,ll y){
    ll k = log2(y-x+1);
    pair<ll,ll> temp1 = st[x][k];
    pair<ll,ll> temp2 = st[y-(1 << k)+1][k];
    if (temp1.first < temp2.first){
        return temp1.second;
    } else {
        return temp2.second;
    }
} 

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >>n;
    graph.resize(n+1);
    parent.resize(n+1,0);
    map <pair<ll,ll>,ll> edge;
    for (int z=0;z<n-1;z++){
        ll a,b;
        cin >>a >> b;
        graph[a].push_back(b);
    }
    height.resize(n+1);
    index.resize(n+1);
    st.resize(n,vector<pair<ll,ll>>(log2(n)));
    dfs();
    build();
    ll m;
    cin >> m;
    for (int z=0;z<m;z++){
        string a;
        cin >> a;
        ll u,v,w;
        cin >> u >> v >> w;
        if (a == "M"){
            ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
            while (u != t){
                pair <ll,ll> temp;
                if (u < parent[u]){
                    temp = make_pair(u,parent[u]);
                } else {
                    temp = make_pair(parent[u],u);
                }
                if (!edge[temp]) edge[temp] = w;
                edge[temp] = min(edge[temp],w);
                u = parent[u];
            }
            while (v != t){
                pair <ll,ll> temp;
                if (v < parent[v]){
                    temp = make_pair(v,parent[v]);
                } else {
                    temp = make_pair(parent[v],v);
                }
                if (!edge[temp]) edge[temp] = w;
                edge[temp] = min(edge[temp],w);
                v = parent[v];
            }
        } else {
            ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
            while (u != t){
                pair <ll,ll> temp;
                if (u < parent[u]){
                    temp = make_pair(u,parent[u]);
                } else {
                    temp = make_pair(parent[u],u);
                }
                if (!edge[temp]) edge[temp] = w;
                edge[temp] = max(edge[temp],w);
                u = parent[u];
            }
            while (v != t){
                pair <ll,ll> temp;
                if (v < parent[v]){
                    temp = make_pair(v,parent[v]);
                } else {
                    temp = make_pair(parent[v],v);
                }
                if (!edge[temp]) edge[temp] = w;
                edge[temp] = max(edge[temp],w);
                v = parent[v];
            }
        }
    }
    for (auto it = edge.begin();it != edge.end();it++){
        cout << (it->first).first << " " << (it->first).second << " " << it->second << endl;
    }
}

Compilation message

minmaxtree.cpp:18:13: error: 'std::vector<long long int> index' redeclared as different kind of symbol
 vector <ll> index;
             ^~~~~
In file included from /usr/include/c++/7/cstring:42:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:48,
                 from minmaxtree.cpp:1:
/usr/include/string.h:477:1: note: previous declaration 'const char* index(const char*, int)'
 index (const char *__s, int __c) __THROW
 ^~~~~
minmaxtree.cpp: In function 'void dfs(ll, ll, ll)':
minmaxtree.cpp:26:12: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
     index[v] = euler.size()-1;
            ^
minmaxtree.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int z=0;z<graph[v].size();z++){
                  ~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:77:11: error: overloaded function with no contextual type information
     index.resize(n+1);
           ^~~~~~
minmaxtree.cpp:89:35: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                   ^
minmaxtree.cpp:89:44: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                            ^
minmaxtree.cpp:89:58: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                                          ^
minmaxtree.cpp:89:67: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                                                   ^
minmaxtree.cpp:113:35: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                   ^
minmaxtree.cpp:113:44: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                            ^
minmaxtree.cpp:113:58: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                                          ^
minmaxtree.cpp:113:67: error: invalid types '<unresolved overloaded function type>[ll {aka long long int}]' for array subscript
             ll t = lca(min(index[u],index[v]),max(index[u],index[v]));
                                                                   ^