oj.uz

Submission #1096573

# Submission time Handle Problem Language Result Execution time Memory
1096573 2024-10-04T19:46:29 Z AlgorithmWarrior Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 879 ms 158548 KB 
#include <bits/stdc++.h>
#define MAX 1000005

using namespace std;

vector<int>tree[MAX];
bool on_path[MAX];
int dp[MAX];
int h[MAX];
int tata[MAX];

int n,t,m;

void read(){
    cin>>n>>t>>m;
    int i;
    for(i=1;i<n;++i){
        int a,b;
        cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
}

void dfs(int nod){
    for(auto fiu : tree[nod])
    if(fiu!=tata[nod]){
        h[fiu]=h[nod]+1;
        tata[fiu]=nod;
        dfs(fiu);
    }
}

void dfs_dp(int nod,int tata){
    int first_val=0,second_val=0;
    for(auto fiu : tree[nod])
    if(fiu!=tata && !on_path[fiu]){
        dfs_dp(fiu,nod);
        ++dp[nod];
        if(dp[fiu]>first_val){
            second_val=first_val;
            first_val=dp[fiu];
        }
        else
            if(dp[fiu]>second_val)
                second_val=dp[fiu];
    }
    dp[nod]+=second_val;
}

int lca(int nod1,int nod2){
    while(nod1!=nod2){
        if(h[nod1]>h[nod2])
            nod1=tata[nod1];
        else
            nod2=tata[nod2];
    }
    return nod1;
}

vector<int>path(int nod1,int nod2){
    int lc=lca(nod1,nod2);
    vector<int>pth1,pth2;
    while(nod1!=lc){
        nod1=tata[nod1];
        pth1.push_back(nod1);
    }
    while(nod2!=lc){
        pth2.push_back(nod2);
        nod2=tata[nod2];
    }
    reverse(pth2.begin(),pth2.end());
    for(auto el : pth2){
        pth1.push_back(el);
    }
    return pth1;
}

int v[MAX];
int add[MAX];
int order[MAX];
int order_rev[MAX];
int sum[MAX];
int psz;
int ind;

bool check_sum(){
    int i;
    int s=0;
    for(i=1;i<=psz;++i){
        s+=sum[i];
        if(s>i)
            return 0;
    }
    return 1;
}

void get_son(int nod){
    for(auto fiu : tree[nod]){
        if(!on_path[fiu]){
            v[++ind]=dp[fiu];
        }
    }
}

void init_dfs_dp(){
    int nod1=m,nod2=t;
    on_path[m]=on_path[t]=1;
    while(nod1!=nod2){
        if(h[nod1]>h[nod2]){
            nod1=tata[nod1];
            on_path[nod1]=1;
        }
        else{
            nod2=tata[nod2];
            on_path[nod2]=1;
        }
    }
    int i,j;
    for(i=1;i<=n;++i)
        if(on_path[i])
            dfs_dp(i,0);
    vector<int>pth=path(t,m);
    for(i=0;i<pth.size();++i){
        get_son(pth[i]);
        add[i+1]=ind;
        for(j=add[i]+1;j<=add[i+1];++j){
            v[j]+=add[i+1];
            order[j]=i+1;
        }
    }
    for(i=1;i<=ind;++i)
        order_rev[i]=pth.size()+1-order[i];
    psz=pth.size();
}

int get_max(){
    int i;
    int id=0;
    for(i=1;i<=ind;++i)
        if(v[id]<v[i])
            id=i;
    return id;
}

int solve(){
    int rasp=0;
    int luate=0;
    while(check_sum() && luate<ind){
        ++luate;
        int id=get_max();
        rasp=v[id];
        v[id]=-2e9;
        int idcur=order[id];
        int i;
        for(i=1;i<=add[idcur-1];++i)
            ++v[i];
        int idcurrev=order_rev[id];
        ++sum[idcurrev];
    }
    if(check_sum())
        return ind;
    return rasp;
}

void write(){
    cout<<solve();
}

int main()
{
    read();
    dfs(1);
    init_dfs_dp();
    write();
    return 0;
}

Compilation message

mousetrap.cpp: In function 'void init_dfs_dp()':
mousetrap.cpp:124:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(i=0;i<pth.size();++i){
      |             ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23956 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23804 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23792 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 77396 KB Output is correct
2 Correct 418 ms 71764 KB Output is correct
3 Correct 813 ms 78144 KB Output is correct
4 Correct 325 ms 51284 KB Output is correct
5 Correct 879 ms 78164 KB Output is correct
6 Correct 818 ms 78160 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23956 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23804 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23792 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 10 ms 23900 KB Output is correct
12 Correct 9 ms 23980 KB Output is correct
13 Correct 9 ms 23932 KB Output is correct
14 Correct 9 ms 23900 KB Output is correct
15 Correct 9 ms 23840 KB Output is correct
16 Correct 9 ms 23908 KB Output is correct
17 Correct 10 ms 23932 KB Output is correct
18 Correct 9 ms 23932 KB Output is correct
19 Correct 10 ms 23896 KB Output is correct
20 Correct 9 ms 23896 KB Output is correct
21 Correct 9 ms 23896 KB Output is correct
22 Correct 10 ms 23900 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23956 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23900 KB Output is correct
4 Correct 10 ms 23804 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23792 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 11 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 454 ms 77396 KB Output is correct
12 Correct 418 ms 71764 KB Output is correct
13 Correct 813 ms 78144 KB Output is correct
14 Correct 325 ms 51284 KB Output is correct
15 Correct 879 ms 78164 KB Output is correct
16 Correct 818 ms 78160 KB Output is correct
17 Correct 10 ms 23900 KB Output is correct
18 Correct 9 ms 23980 KB Output is correct
19 Correct 9 ms 23932 KB Output is correct
20 Correct 9 ms 23900 KB Output is correct
21 Correct 9 ms 23840 KB Output is correct
22 Correct 9 ms 23908 KB Output is correct
23 Correct 10 ms 23932 KB Output is correct
24 Correct 9 ms 23932 KB Output is correct
25 Correct 10 ms 23896 KB Output is correct
26 Correct 9 ms 23896 KB Output is correct
27 Correct 9 ms 23896 KB Output is correct
28 Correct 10 ms 23900 KB Output is correct
29 Correct 10 ms 23984 KB Output is correct
30 Correct 463 ms 80192 KB Output is correct
31 Correct 463 ms 80212 KB Output is correct
32 Correct 564 ms 154048 KB Output is correct
33 Correct 515 ms 158548 KB Output is correct
34 Correct 832 ms 81200 KB Output is correct
35 Correct 857 ms 81284 KB Output is correct
36 Correct 789 ms 91084 KB Output is correct
37 Correct 805 ms 90956 KB Output is correct
38 Correct 636 ms 92356 KB Output is correct
39 Correct 692 ms 92448 KB Output is correct
40 Correct 621 ms 92368 KB Output is correct