oj.uz

답안 #851167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851167 2023-09-18T17:37:41 Z Charizard2021 Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 2000 ms 14168 KB 
#include <bits/stdc++.h>
using namespace std;
const long long N = 200001;
vector<long long> adj[N];
vector<long long> depth(N);
long long parents[N][18];
vector<long long> parent(N);
vector<long long> maxVal(N);
vector<long long> h(N);
vector<long long> sz(N);
void dfs(long long u, long long p){
    for(long long v : adj[u]){
        if(v != p){
            parents[v][0] = u;
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}
long long distance(long long a, long long b){
    long long dist = depth[a] + depth[b];
    if(depth[a] < depth[b]){
        swap(a, b);
    }
    long long diff = depth[a] - depth[b];
    long long val = 0;
    while(diff > 0){
        if(diff & 1){
            a = parents[a][val];
        }
        diff /= 2;
        val++;
    }
    if(a == b){
        return dist - 2 * depth[a];
    }
    for(long long i = 16; i >= 0; i++){
        if(parents[a][i] != parents[b][i]){
            a = parents[a][i];
            b = parents[b][i];
        }
    }
    return dist - 2 * depth[a] + 2;
}
long long getRoot(long long u){
    if(parent[u] == u){
        return u;
    }
    return parent[u] = getRoot(parent[u]);
}
void unite(long long a, long long b){
    long long u = getRoot(a);
    long long v = getRoot(b);
    if(u == v){
        return;
    }
    if(sz[u] == sz[v]){
        sz[u]++;
    }
    if(sz[u] > sz[v]){
        parent[v] = u;
        if(h[maxVal[v]] > h[maxVal[u]]){
            maxVal[u] = maxVal[v];
        }
    }
    else{
        parent[u] = v;
        if(h[maxVal[u]] > h[maxVal[v]]){
            maxVal[v] = maxVal[u];
        }
    }
}
int main(){
    long long n;
    cin >> n;
    for(long long i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(long long i = 0; i < n - 1; i++){
        long long a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    parents[1][0] = 1;
    dfs(1, 0);
    for(long long j = 1; j <= 18; j++){
        for(long long i = 1; i <= n; i++){
            parents[i][j] = parents[parents[i][j - 1]][j - 1];
        }
    }
    for(long long i = 1; i <= n; i++){
        parent[i] = i;
        maxVal[i] = i;
    }
    vector<pair<long long, long long> > adj2[1 + n];
    vector<pair<long long, long long> > positions(1 + n);
    for(long long i = 1; i <= n; i++){
        positions[i] = make_pair(h[i], i);
    }
    sort(positions.begin(), positions.end());
    for(long long i = 1; i <= n; i++){
        long long u = positions[i].second;
        for(long long v : adj[u]){
            if(h[v] <= h[u]){
                long long weight = maxVal[getRoot(v)];
                adj2[u].push_back(make_pair(weight, distance(u, weight)));
                unite(u, v);
            }
        }
    }
    vector<long long> dist(1 + n);
    vector<bool> visited(1 + n, false);
    queue<long long> q;
    q.push(positions[n].second);
    while(!q.empty()){
        long long u = q.front();
        q.pop();
        visited[u] = true;
        for(pair<long long, long long> x : adj2[u]){
            long long v = x.first;
            if(!visited[v]){
                visited[v] = true;
                dist[v] = dist[u] + x.second;
                q.push(v);
            }
        }
    }
    long long ans = 0;
    for(long long i = 1; i <= n; i++){
        ans = max(ans, dist[i]);
    }
    cout << ans << "\n";
}

Compilation message

Main.cpp: In function 'long long int distance(long long int, long long int)':
Main.cpp:37:5: warning: iteration 9223372036854775791 invokes undefined behavior [-Waggressive-loop-optimizations]
   37 |     for(long long i = 16; i >= 0; i++){
      |     ^~~
Main.cpp:37:29: note: within this loop
   37 |     for(long long i = 16; i >= 0; i++){
      |                           ~~^~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

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