oj.uz

Submission #920445

# Submission time Handle Problem Language Result Execution time Memory
920445 2024-02-02T14:44:31 Z Ludissey Cat Exercise (JOI23_ho_t4) C++14
100 / 100
 804 ms 148176 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> adj;
int n; 
const int LOG=63;
vector<int> p;
vector<int> depth;
vector<bool> proc;
vector<bool> visited;
vector<int> parent;
vector<vector<pair<int,int>>> child;
vector<vector<int>> ancestors;
vector<int> sz;

int lca(int a, int b){
    if(depth[b]>depth[a]) swap(a,b);
    int k=depth[a]-depth[b];
    for (int j = LOG-1; j >= 0; j--)
    {
        if(k&((long long)1<<j)) a=ancestors[a][j];
    }
    if(a==b) return a;
    for (int j = LOG-1; j >= 0; j--)
    {
        if(ancestors[a][j]!=ancestors[b][j]) {
            a=ancestors[a][j];
            b=ancestors[b][j];
        }
    }
    return ancestors[a][0];
}

void setup_ancestors(){
    for (int k = 1; k < LOG; k++)
    {
        for (int i = 0; i < n; i++)
        {
            ancestors[i][k]=ancestors[ancestors[i][k-1]][k-1];
        }
    }
}

int getParent(int a) {
    if(a==parent[a]) return a;
    return parent[a]=getParent(parent[a]);
}

void unify(int a, int b){
    a=getParent(a);
    b=getParent(b);
    if(a==b) return;
    int lc=lca(a,b);
    int dist=(depth[a]+depth[b])-(2*depth[lc]);
    parent[b]=a;
    child[a].push_back({b,dist});
    sz[a]+=sz[b];
}

void reconstructTree(){
    vector<pair<int,int>> _p;
    for (int i = 0; i < n; i++) _p.push_back({p[i], i});
    sort(_p.begin(), _p.end());
    for (int i = 0; i < n; i++)
    {
        for (auto u : adj[_p[i].second])
        {
            if(proc[u]) unify(_p[i].second, getParent(u));
        }
        proc[_p[i].second]=true;
    }
}

void smltree(int i, int dpth){
    if(visited[i]) return;
    visited[i]=true;
    depth[i]=dpth;
    for (auto u : adj[i]) {
        if(visited[u]) continue;
        ancestors[u][0]=i;
        smltree(u, depth[i]+1);
    }
}

int dfs(int i){
    int sum=0;
    if(visited[i]) return 0;
    visited[i]=true;
    if(child[i].size()==0) return 0;
    for (auto u : child[i]) {
        sum=max(sum, dfs(u.first)+u.second);
    }
    return sum;
}

signed main() {
	// Input:
    cin >> n;

    p.resize(n);
    visited.resize(n, false);
    parent.resize(n);
    child.resize(n);
    proc.resize(n);
    depth.resize(n);
    sz.resize(n, 1);
    adj.resize(n);

    int start;
    for (int i = 0; i < n; i++){
        cin >> p[i];
        if (p[i] == n) start = i;
        parent[i]=i;
    }
    for (int i = 0; i < n-1; i++)
    {
        int a,b; cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }


    ancestors.resize(n, vector<int>(LOG, start));
    smltree(start,0);
    setup_ancestors();
    reconstructTree();
    visited.clear();
    visited.resize(n, false);
    cout << dfs(start) << "\n";
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:131:22: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |     cout << dfs(start) << "\n";
      |                      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 7 ms 3932 KB Output is correct
19 Correct 7 ms 3928 KB Output is correct
20 Correct 7 ms 3928 KB Output is correct
21 Correct 7 ms 3928 KB Output is correct
22 Correct 9 ms 3944 KB Output is correct
23 Correct 8 ms 3932 KB Output is correct
24 Correct 7 ms 3936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 7 ms 3932 KB Output is correct
19 Correct 7 ms 3928 KB Output is correct
20 Correct 7 ms 3928 KB Output is correct
21 Correct 7 ms 3928 KB Output is correct
22 Correct 9 ms 3944 KB Output is correct
23 Correct 8 ms 3932 KB Output is correct
24 Correct 7 ms 3936 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 8 ms 3932 KB Output is correct
27 Correct 12 ms 3928 KB Output is correct
28 Correct 9 ms 4024 KB Output is correct
29 Correct 8 ms 3932 KB Output is correct
30 Correct 8 ms 3852 KB Output is correct
31 Correct 9 ms 3928 KB Output is correct
32 Correct 9 ms 3932 KB Output is correct
33 Correct 8 ms 3852 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 7 ms 3932 KB Output is correct
19 Correct 7 ms 3928 KB Output is correct
20 Correct 7 ms 3928 KB Output is correct
21 Correct 7 ms 3928 KB Output is correct
22 Correct 9 ms 3944 KB Output is correct
23 Correct 8 ms 3932 KB Output is correct
24 Correct 7 ms 3936 KB Output is correct
25 Correct 582 ms 148176 KB Output is correct
26 Correct 571 ms 147772 KB Output is correct
27 Correct 564 ms 147780 KB Output is correct
28 Correct 624 ms 144572 KB Output is correct
29 Correct 619 ms 145960 KB Output is correct
30 Correct 625 ms 145608 KB Output is correct
31 Correct 608 ms 146080 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 664 ms 139392 KB Output is correct
4 Correct 664 ms 139284 KB Output is correct
5 Correct 670 ms 139520 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 500 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 7 ms 3932 KB Output is correct
19 Correct 7 ms 3928 KB Output is correct
20 Correct 7 ms 3928 KB Output is correct
21 Correct 7 ms 3928 KB Output is correct
22 Correct 9 ms 3944 KB Output is correct
23 Correct 8 ms 3932 KB Output is correct
24 Correct 7 ms 3936 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 8 ms 3932 KB Output is correct
27 Correct 12 ms 3928 KB Output is correct
28 Correct 9 ms 4024 KB Output is correct
29 Correct 8 ms 3932 KB Output is correct
30 Correct 8 ms 3852 KB Output is correct
31 Correct 9 ms 3928 KB Output is correct
32 Correct 9 ms 3932 KB Output is correct
33 Correct 8 ms 3852 KB Output is correct
34 Correct 582 ms 148176 KB Output is correct
35 Correct 571 ms 147772 KB Output is correct
36 Correct 564 ms 147780 KB Output is correct
37 Correct 624 ms 144572 KB Output is correct
38 Correct 619 ms 145960 KB Output is correct
39 Correct 625 ms 145608 KB Output is correct
40 Correct 608 ms 146080 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 664 ms 139392 KB Output is correct
44 Correct 664 ms 139284 KB Output is correct
45 Correct 670 ms 139520 KB Output is correct
46 Correct 722 ms 146112 KB Output is correct
47 Correct 804 ms 146040 KB Output is correct
48 Correct 791 ms 146140 KB Output is correct
49 Correct 740 ms 145416 KB Output is correct
50 Correct 801 ms 139300 KB Output is correct
51 Correct 765 ms 139480 KB Output is correct
52 Correct 753 ms 138628 KB Output is correct
53 Correct 800 ms 139356 KB Output is correct