oj.uz

Submission #957100

# Submission time Handle Problem Language Result Execution time Memory
957100 2024-04-03T01:41:53 Z VinhLuu Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 414 ms 83932 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[u] < sz[v]) swap(u, v);
    pa[v] = u;
    sz[u] += sz[v];
    if(a[val[v]] > a[val[u]]) val[u] = val[v];
//    cerr << val[u] << " e\n";
}

void edge(int u,int v){
    int w = cal(u, v);
//    cerr << u << " " << v << " " << w << " r\n";
    p[u].pb({v, w});
}

void add(int u){
    open[u] = 1;
    for(auto j : g[u]){
        if(!open[j]) continue;
        edge(u, val[fin(j)]);
    }
    for(auto j : g[u]){
        if(!open[j]) continue;
        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 ++){
//        cerr << c[i] << " add\n";
        add(c[i]);
    }
//    cout << "\n";

    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:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Correct 4 ms 23024 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 5 ms 22956 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Correct 4 ms 23024 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 5 ms 22956 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 4 ms 22872 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct
15 Correct 4 ms 22872 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 4 ms 22876 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Correct 4 ms 23024 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 5 ms 22956 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 4 ms 22872 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct
15 Correct 4 ms 22872 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 4 ms 22876 KB Output is correct
18 Correct 7 ms 25692 KB Output is correct
19 Correct 7 ms 25692 KB Output is correct
20 Correct 7 ms 25692 KB Output is correct
21 Correct 9 ms 25692 KB Output is correct
22 Correct 7 ms 25692 KB Output is correct
23 Correct 8 ms 25700 KB Output is correct
24 Correct 8 ms 25688 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Correct 4 ms 23024 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 5 ms 22956 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 4 ms 22872 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct
15 Correct 4 ms 22872 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 4 ms 22876 KB Output is correct
18 Correct 7 ms 25692 KB Output is correct
19 Correct 7 ms 25692 KB Output is correct
20 Correct 7 ms 25692 KB Output is correct
21 Correct 9 ms 25692 KB Output is correct
22 Correct 7 ms 25692 KB Output is correct
23 Correct 8 ms 25700 KB Output is correct
24 Correct 8 ms 25688 KB Output is correct
25 Correct 4 ms 22876 KB Output is correct
26 Correct 8 ms 25692 KB Output is correct
27 Correct 8 ms 25692 KB Output is correct
28 Correct 9 ms 25688 KB Output is correct
29 Correct 9 ms 25912 KB Output is correct
30 Correct 8 ms 25436 KB Output is correct
31 Correct 9 ms 25436 KB Output is correct
32 Correct 8 ms 25436 KB Output is correct
33 Correct 8 ms 25436 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Correct 4 ms 23024 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 5 ms 22956 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 4 ms 22872 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct
15 Correct 4 ms 22872 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 4 ms 22876 KB Output is correct
18 Correct 7 ms 25692 KB Output is correct
19 Correct 7 ms 25692 KB Output is correct
20 Correct 7 ms 25692 KB Output is correct
21 Correct 9 ms 25692 KB Output is correct
22 Correct 7 ms 25692 KB Output is correct
23 Correct 8 ms 25700 KB Output is correct
24 Correct 8 ms 25688 KB Output is correct
25 Correct 194 ms 83820 KB Output is correct
26 Correct 187 ms 83932 KB Output is correct
27 Correct 158 ms 83644 KB Output is correct
28 Correct 244 ms 82768 KB Output is correct
29 Correct 239 ms 82772 KB Output is correct
30 Correct 242 ms 82788 KB Output is correct
31 Correct 252 ms 83328 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 224 ms 75812 KB Output is correct
4 Correct 274 ms 75912 KB Output is correct
5 Correct 215 ms 75788 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 22872 KB Output is correct
4 Correct 4 ms 23024 KB Output is correct
5 Correct 4 ms 22876 KB Output is correct
6 Correct 4 ms 22876 KB Output is correct
7 Correct 4 ms 22876 KB Output is correct
8 Correct 4 ms 22872 KB Output is correct
9 Correct 4 ms 22876 KB Output is correct
10 Correct 5 ms 22956 KB Output is correct
11 Correct 4 ms 22876 KB Output is correct
12 Correct 5 ms 22876 KB Output is correct
13 Correct 4 ms 22872 KB Output is correct
14 Correct 4 ms 22876 KB Output is correct
15 Correct 4 ms 22872 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 4 ms 22876 KB Output is correct
18 Correct 7 ms 25692 KB Output is correct
19 Correct 7 ms 25692 KB Output is correct
20 Correct 7 ms 25692 KB Output is correct
21 Correct 9 ms 25692 KB Output is correct
22 Correct 7 ms 25692 KB Output is correct
23 Correct 8 ms 25700 KB Output is correct
24 Correct 8 ms 25688 KB Output is correct
25 Correct 4 ms 22876 KB Output is correct
26 Correct 8 ms 25692 KB Output is correct
27 Correct 8 ms 25692 KB Output is correct
28 Correct 9 ms 25688 KB Output is correct
29 Correct 9 ms 25912 KB Output is correct
30 Correct 8 ms 25436 KB Output is correct
31 Correct 9 ms 25436 KB Output is correct
32 Correct 8 ms 25436 KB Output is correct
33 Correct 8 ms 25436 KB Output is correct
34 Correct 194 ms 83820 KB Output is correct
35 Correct 187 ms 83932 KB Output is correct
36 Correct 158 ms 83644 KB Output is correct
37 Correct 244 ms 82768 KB Output is correct
38 Correct 239 ms 82772 KB Output is correct
39 Correct 242 ms 82788 KB Output is correct
40 Correct 252 ms 83328 KB Output is correct
41 Correct 4 ms 22876 KB Output is correct
42 Correct 5 ms 22876 KB Output is correct
43 Correct 224 ms 75812 KB Output is correct
44 Correct 274 ms 75912 KB Output is correct
45 Correct 215 ms 75788 KB Output is correct
46 Correct 381 ms 81304 KB Output is correct
47 Correct 400 ms 81112 KB Output is correct
48 Correct 380 ms 81108 KB Output is correct
49 Correct 414 ms 81236 KB Output is correct
50 Correct 340 ms 74756 KB Output is correct
51 Correct 328 ms 74712 KB Output is correct
52 Correct 325 ms 74696 KB Output is correct
53 Correct 332 ms 74964 KB Output is correct