oj.uz

Submission #145148

# Submission time Handle Problem Language Result Execution time Memory
145148 2019-08-18T22:10:15 Z MKopchev Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 634 ms 39132 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=7e4+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[nmax];

bool solve(int node)
{
    if(been[node-n])return 0;
    been[node-n]=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 8 ms 5624 KB Output is correct
2 Correct 8 ms 5628 KB Output is correct
3 Correct 6 ms 5624 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 35452 KB Output is correct
2 Correct 483 ms 33400 KB Output is correct
3 Correct 466 ms 33860 KB Output is correct
4 Correct 521 ms 36048 KB Output is correct
5 Correct 482 ms 33796 KB Output is correct
6 Correct 526 ms 34040 KB Output is correct
7 Correct 458 ms 33400 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 29352 KB Output is correct
2 Correct 258 ms 29448 KB Output is correct
3 Correct 239 ms 30544 KB Output is correct
4 Correct 211 ms 31352 KB Output is correct
5 Correct 263 ms 30200 KB Output is correct
6 Correct 283 ms 30456 KB Output is correct
7 Correct 269 ms 30052 KB Output is correct
8 Correct 263 ms 29688 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5624 KB Output is correct
2 Correct 8 ms 5628 KB Output is correct
3 Correct 6 ms 5624 KB Output is correct
4 Correct 6 ms 5624 KB Output is correct
5 Correct 501 ms 35452 KB Output is correct
6 Correct 483 ms 33400 KB Output is correct
7 Correct 466 ms 33860 KB Output is correct
8 Correct 521 ms 36048 KB Output is correct
9 Correct 482 ms 33796 KB Output is correct
10 Correct 526 ms 34040 KB Output is correct
11 Correct 458 ms 33400 KB Output is correct
12 Correct 285 ms 29352 KB Output is correct
13 Correct 258 ms 29448 KB Output is correct
14 Correct 239 ms 30544 KB Output is correct
15 Correct 211 ms 31352 KB Output is correct
16 Correct 263 ms 30200 KB Output is correct
17 Correct 283 ms 30456 KB Output is correct
18 Correct 269 ms 30052 KB Output is correct
19 Correct 263 ms 29688 KB Output is correct
20 Correct 522 ms 35884 KB Output is correct
21 Correct 433 ms 34296 KB Output is correct
22 Correct 430 ms 34552 KB Output is correct
23 Correct 442 ms 34372 KB Output is correct
24 Correct 526 ms 38136 KB Output is correct
25 Correct 589 ms 39132 KB Output is correct
26 Correct 550 ms 38444 KB Output is correct
27 Correct 612 ms 37924 KB Output is correct
28 Correct 532 ms 36324 KB Output is correct
29 Correct 634 ms 36368 KB Output is correct
30 Correct 521 ms 34852 KB Output is correct
31 Correct 560 ms 35192 KB Output is correct
32 Correct 555 ms 36092 KB Output is correct
33 Correct 515 ms 35336 KB Output is correct
34 Correct 518 ms 35292 KB Output is correct
35 Correct 489 ms 34680 KB Output is correct