oj.uz

Submission #145144

# Submission time Handle Problem Language Result Execution time Memory
145144 2019-08-18T21:40:39 Z MKopchev Min-max tree (BOI18_minmaxtree) C++14
22 / 100
 204 ms 33656 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42,inf=1e9;
int n;
vector<int> adj[nmax];
int parent[nmax];
int up[20][nmax],depth[nmax];
void dfs(int node,int par)
{
    up[0][node]=par;
    for(auto k:adj[node])
        if(k!=par)
        {
            depth[k]=depth[node]+1;
            dfs(k,node);
        }
}
int lca(int u,int v)
{
    if(depth[u]>depth[v])swap(u,v);

    for(int i=19;i>=0;i--)
        if(depth[v]-(1<<i)>=depth[u])v=up[i][v];

    if(u==v)return u;
    for(int i=19;i>=0;i--)
        if(up[i][u]!=up[i][v])
        {
            u=up[i][u];
            v=up[i][v];
        }

    return up[0][u];
}
int dist(int u,int v)
{
    return depth[u]+depth[v]-2*depth[lca(u,v)];
}

int min_max[20][nmax];
void make_line(int low,int upper,int cost)
{
    if(low==upper)return;

    int d=dist(low,upper);
    for(int i=19;i>=0;i--)
        if(((1<<i)&d))
        {
            min_max[i][low]=min(min_max[i][low],cost);
            //cout<<"min_max "<<i<<" "<<low<<" "<<cost<<endl;
            low=up[i][low];
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin>>n;
    for(int i=0;i<20;i++)
        for(int j=1;j<=n;j++)
            min_max[i][j]=inf;

    int u,v;
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1,1);

    for(int st=1;st<20;st++)
        for(int i=1;i<=n;i++)
        {
            up[st][i]=up[st-1][up[st-1][i]];
            //cout<<st<<" "<<i<<" -> "<<up[st][i]<<endl;
        }

    int q,c;
    char type;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>type>>u>>v>>c;
        assert(type=='M');

        int l=lca(u,v);
        make_line(u,l,c);
        make_line(v,l,c);
    }

    for(int i=19;i>0;i--)
    {
        for(int j=1;j<=n;j++)
        {
            min_max[i-1][up[i-1][j]]=min(min_max[i-1][up[i-1][j]],min_max[i][j]);
            min_max[i-1][j]=min(min_max[i-1][j],min_max[i][j]);
        }
        /*
        for(int j=1;j<=n;j++)
            cout<<i<<" "<<j<<" "<<min_max[i][j]<<endl;
        cout<<"---"<<endl;
        */
    }
    for(int i=2;i<=n;i++)
        cout<<up[0][i]<<" "<<i<<" "<<min_max[0][i]<<"\n";
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 22000 KB Output is correct
2 Correct 157 ms 19976 KB Output is correct
3 Correct 204 ms 20984 KB Output is correct
4 Correct 149 ms 22524 KB Output is correct
5 Correct 150 ms 20728 KB Output is correct
6 Correct 139 ms 20472 KB Output is correct
7 Correct 128 ms 19960 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 68 ms 33656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 5624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -