글 읽기 - 혹시 예제가 더 있을까요? 왜 계속 틀리는지 모르겠네요..

sopp0002 3년 전 0

제가 나름 예제를 계속만들어서 테스트 해보는데 그건 다 맞고 막상 넣으면 다 틀리네요..

틀릴만한 예제가 더 있을까요?

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

int N,M;
const int MAXN=100000+1;
struct Edge{
    int i;
    int j;
    int w;
};
vector<pair<int, int>> adj[MAXN];
vector<int> chain[MAXN];
int parent[MAXN];
int sz[MAXN];
int *tree;
int depth[MAXN];
int chain_number[MAXN];
int chain_index[MAXN];
int cur_dfs_order=1;
int dfs_order[MAXN];
int tree_size;


int dfs(int i, int p){
    parent[i] = p;
    sz[i] = 1;
    dfs_order[i] = cur_dfs_order++;
    for(int x=0; x<adj[i].size(); x++){
        if(adj[i][x].first != p){
            sz[i] += dfs(adj[i][x].first, i);
        }
    }
    return sz[i];
}

//current index, parent, chain number, depth
void HLD(int i, int p, int cur_chain, int d){
    depth[i] = d;
    chain_number[i] = cur_chain;
    chain_index[i] = chain[cur_chain].size();
    chain[cur_chain].push_back(i);
    
    int heavy = -1;
    for(int k=0; k<adj[i].size(); k++){
        if(adj[i][k].first!=p && (heavy == -1 || sz[heavy] < sz[adj[i][k].first])){
            heavy = adj[i][k].first;
        }
    }
    if(heavy != -1){
        HLD(heavy, i, cur_chain, d);
    }

    for(int k=0; k<adj[i].size(); k++){
        if(heavy != adj[i][k].first && adj[i][k].first != p)
            HLD(adj[i][k].first, i, adj[i][k].first, d+1);
    }
}
// lowest comman ancestor
int LCA(int i, int j){
    while(chain_number[i] != chain_number[j]){
        if(depth[i] > depth[j]){
            i = parent[chain_number[i]];
        }else{
            j = parent[chain_number[j]];
        }
    }
    return chain_index[i]>chain_index[j] ? j : i;
}
void tree_init(Edge *edges){
    int lim = tree_size/2;
    
    for(int i=1; i<N; i++){
        int idx = dfs_order[edges[i].j];
        if(dfs_order[edges[i].i] > dfs_order[edges[i].j]){
            idx = dfs_order[edges[i].i];
        }
        idx+=lim;
        tree[idx]=edges[i].w;
        while(idx>1){
            idx /= 2;
            tree[idx]=max(tree[idx*2], tree[idx*2+1]);
        }
    }
}
void update(Edge *edges, int i, int v){
    edges[i].w = v;
    int idx = dfs_order[edges[i].j];
    if(dfs_order[edges[i].i] > dfs_order[edges[i].j]){
        idx = dfs_order[edges[i].i];
    }
    idx += tree_size/2;
    tree[idx] = edges[i].w;
    while(idx>1){
        idx/=2;
        tree[idx]=max(tree[idx*2], tree[idx*2+1]);
    }
}

int chain_query(int s, int e){
    s = dfs_order[s];
    e = dfs_order[e];
    int result = -99999;
    int lim = tree_size/2;
    s += lim;
    e += lim;
    while(s<e){
        if(s%2 == 1)
            result = max(result, tree[s++]);
        if(e%2 == 0)
            result = max(result, tree[e--]);
        s /= 2;
        e /= 2;
    }
    if(s==e)
        result = max(result, tree[s]);
    return result;
}

int sub_query(int i, int j){
    int result = -99999;
    while(chain_number[i] != chain_number[j]){
        if(depth[i] > depth[j]){
            int cHead = chain[chain_number[i]][0];
            result = max(result, chain_query(cHead, i));
            i = parent[chain_number[i]];
        }else{
            int cHead = chain[chain_number[j]][0];
            result = max(result, chain_query(cHead, j));
            j = parent[chain_number[j]];
        }
    }
    if(chain_index[i] > chain_index[j]) swap(i,j);
    result = max(result, chain_query(i, j));
    return result;
}

int find_max_edge(int i, int j){
    int lca = LCA(i, j);
    int result = max(sub_query(i, lca), sub_query(j, lca));
    return result;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> N;
    Edge *edges = new Edge [N];
    tree_size = pow(2, log2(N)+1);
    tree = new int [tree_size+1];
    fill(tree, tree+tree_size+1, -1);
    for(int i=1; i<N; i++){
        int a,b,c;
        cin >> a >> b >> c;
        edges[i].i=a;
        edges[i].j=b;
        edges[i].w=c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1, 0);
    HLD(1, 0, 1, 1);

    tree_init(edges);

    cin >> M;
    for(int i=0; i<M; i++){
        int a,b,c;
        cin >> a >> b >> c;
        if(a==1){
            update(edges, b, c);
        }
        else if(a==2){
            if(b==c){
                cout << 0 <<"\n";
            }else{
                int result = find_max_edge(b, c);
                cout << result << "\n";
            }
        }
    }
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

혹시 예제가 더 있을까요? 왜 계속 틀리는지 모르겠네요..

sopp0002 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말