oj.uz

Submission #145146

# Submission time Handle Problem Language Result Execution time Memory
145146 2019-08-18T22:03:31 Z MKopchev Min-max tree (BOI18_minmaxtree) C++14
36 / 100
 1000 ms 38036 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],max_min[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);
            low=up[i][low];
        }
}

void make_min_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))
        {
            max_min[i][low]=max(max_min[i][low],cost);
            low=up[i][low];
        }
}
map<int,int> seen;

vector<int> matching[2*nmax];

void add_edge(int low,int c)
{
    if(seen.count(c)==0)return;
    //cout<<low<<" "<<seen[c]+n<<endl;
    matching[low].push_back(seen[c]+n);
    matching[seen[c]+n].push_back(low);
}

int match[nmax];
bool been[2*nmax];

bool solve(int node)
{
    if(been[node])return 0;
    been[node]=1;
    for(auto k:matching[node])
        if(match[k]==0||solve(match[k]))
        {
            match[k]=node;
            return 1;
        }
    return 0;
}
int mem_cost[nmax];
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;

        mem_cost[i]=c;

        seen[c]=i;

        int l=lca(u,v);

        if(type=='M')
        {
            make_line(u,l,c);
            make_line(v,l,c);
        }
        else
        {
            make_min_line(u,l,c);
            make_min_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++)
        {
            max_min[i-1][up[i-1][j]]=max(max_min[i-1][up[i-1][j]],max_min[i][j]);
            max_min[i-1][j]=max(max_min[i-1][j],max_min[i][j]);
        }

    }

    for(int i=2;i<=n;i++)
    {
        add_edge(i,min_max[0][i]);
        add_edge(i,max_min[0][i]);
    }

    for(int i=1;i<=q;i++)
    {
        memset(been,0,sizeof(been));

        solve(i+n);
    }
    /*
    for(int i=1;i<=n;i++)
        cout<<i<<" -> "<<match[i]<<endl;
    */

    for(int i=2;i<=n;i++)
        cout<<up[0][i]<<" "<<i<<" "<<(match[i]?mem_cost[match[i]-n]:min_max[0][i])<<"\n";
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7928 KB Output is correct
2 Correct 9 ms 7928 KB Output is correct
3 Correct 11 ms 7800 KB Output is correct
4 Correct 10 ms 7800 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 38036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 31508 KB Output is correct
2 Correct 411 ms 31900 KB Output is correct
3 Correct 369 ms 33016 KB Output is correct
4 Correct 367 ms 33784 KB Output is correct
5 Correct 434 ms 32392 KB Output is correct
6 Correct 501 ms 33016 KB Output is correct
7 Correct 453 ms 32504 KB Output is correct
8 Correct 444 ms 32348 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7928 KB Output is correct
2 Correct 9 ms 7928 KB Output is correct
3 Correct 11 ms 7800 KB Output is correct
4 Correct 10 ms 7800 KB Output is correct
5 Execution timed out 1067 ms 38036 KB Time limit exceeded
6 Halted 0 ms 0 KB -