oj.uz

Submission #957096

# Submission time Handle Problem Language Result Execution time Memory
957096 2024-04-03T01:29:41 Z VinhLuu Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 5 ms 22876 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 2e18;

int n, k, a[N], pa[N], sz[N], val[N], open[N], ans, c[N];
vector<int> g[N];
vector<pii> p[N];

int in[N], en[N], demin, f[N][22], d[N];

void pre(int u,int v){
    in[u] = ++demin;
    if(u == 1) for(int i = 0; i <= 20; i ++) f[u][i] = u;
    else{
        f[u][0] = v;
        for(int i = 1; i <= 20; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(auto j : g[u]){
        if(j == v) continue;
        d[j] = d[u] + 1;
        pre(j, u);
    }
    en[u] = demin;
}
bool kt(int u,int v){
    return in[u] <= in[v] && in[v] <= en[u];
}
int cal(int u,int v){
    int lca = u;
    if(!kt(u, v)){
        int h = u;
        for(int i = 20; i >= 0; i --){
            if(kt(f[h][i], v)) lca = f[h][i];
            else h = f[h][i];
        }
    }
    return d[u] + d[v] - 2 * d[lca];
}

int fin(int u){
    return pa[u] == u ? u : pa[u] = fin(pa[u]);
}

void dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return ;
    if(sz[v] < sz[u]) swap(u, v);
    pa[v] = u;
    sz[u] += sz[v];
    val[u] = max(val[u], val[v]);
}

void edge(int u,int v){
    int w = cal(u, v);
    p[u].pb({v, w});
    p[v].pb({u, w});
}

void add(int u){
    open[u] = 1;
    for(auto j : g[u]){
        if(!open[j]) continue;
        edge(u, val[fin(j)]);
        dsu(u, j);
    }
}

void dfs(int u,int v,int ts){
    ans = max(ans, ts);
    for(auto [j, w] : p[u]){
        if(j == v) continue;
        dfs(j, u, ts + w);
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n;
    for(int i = 1; i <= n; i ++) pa[i] = val[i] = i, sz[i] = 1;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        c[i] = i;
    }
    sort(c + 1, c + n + 1, [&] (int x,int y){return a[x] < a[y];});

    for(int i = 1; i < n; i ++){
        int x, y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    pre(1, 0);

    for(int i = 1; i <= n; i ++) add(c[i]);

    int mx = 0;
    for(int i= 1; i <= n; i ++) if(a[i] > a[mx]) mx = i;
    dfs(mx, 0, 0);
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22876 KB Output is correct
2 Incorrect 4 ms 22876 KB Output isn't correct
3 Halted 0 ms 0 KB -