oj.uz

답안 #137651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137651 2019-07-28T08:15:58 Z mechfrog88 Min-max tree (BOI18_minmaxtree) C++14
0 / 100
 1000 ms 52504 KB 
#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> ind;
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);
    ind[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);
    ind.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(ind[u],ind[v]),max(ind[u],ind[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(ind[u],ind[v]),max(ind[u],ind[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: In function 'void dfs(ll, ll, ll)':
minmaxtree.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int z=0;z<graph[v].size();z++){
                  ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 81 ms 52216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 78 ms 52504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -