oj.uz

답안 #1090798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1090798 2024-09-18T18:41:04 Z KALARRY Min-max tree (BOI18_minmaxtree) C++14
0 / 100
 118 ms 14672 KB 
//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,K,val[70005],par[70005],minim[70005],maxim[70005],s[70005],heavy[70005],head[70005],depth[70005],pos[70005],cur_pos,has_pos[70005],lazy_max[200005],lazy_min[200005];
vector<int> adj[70005];

void dfs(int v,int p)
{
    par[v] = p;
    s[v] = 1;
    depth[v] = depth[p] + 1;

    heavy[v] = -1;
    int max_found = -1;
    for(auto u : adj[v])
    {
        if(u!=p)
        {
            dfs(u,v);
            s[v] += s[u];
            if(s[u] > max_found)
            {
                max_found = s[u];
                heavy[v] = u;
            }
        }
    }
}

void decompose(int v,int h)
{
    pos[v] = ++cur_pos;
    has_pos[cur_pos] = v;
    head[v] = h;
    if(heavy[v] != -1)
        decompose(heavy[v],h);
    for(auto u : adj[v])
        if(u != par[v] && u != heavy[v])
            decompose(u,u);
}

void propagate(int v,int start,int end);

void update(bool max_change,int l,int r,int val,int v = 1,int start = 1,int end = N)
{
    if(start==l && end==r)
    {
        if(max_change)
        {
            if(lazy_max[v]==-1)
                lazy_max[v] = val;
            else
                lazy_max[v] = min(lazy_max[v],val);
        }
        else
        {
            if(lazy_min[v]==-1)
                lazy_min[v] = val;
            else
                lazy_min[v] = max(lazy_min[v],val);
        }
        return;
    }
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(r <= mid)
        update(max_change,l,r,val,2*v,start,mid);
    else if(l > mid)
        update(max_change,l,r,val,2*v+1,mid+1,end);
    else
    {
        update(max_change,l,mid,val,2*v,start,mid);
        update(max_change,mid+1,r,val,2*v+1,mid+1,end);
    }
}

void propagate(int v,int start,int end)
{
    if(lazy_max[v] != -1)
    {
        int mid = (start + end)/2;
        update(true,start,mid,lazy_max[v],2*v,start,mid);
        update(true,mid+1,end,lazy_max[v],2*v+1,mid+1,end);
    }
    if(lazy_min[v] != -1)
    {
        int mid = (start + end)/2;
        update(false,start,mid,lazy_min[v],2*v,start,mid);
        update(false,mid+1,end,lazy_min[v],2*v+1,mid+1,end);    }
}

void update_tree(int a,int b,int val,bool max_change)
{
    while(head[a] != head[b])
    {
        if(depth[a] > depth[b])
            swap(a,b);
        if(max_change)
            update(true,pos[head[b]],pos[b],val);
        else
            update(false,pos[head[b]],pos[b],val);
        b = par[head[b]];
    }
    if(depth[a] > depth[b])
        swap(a,b);
    if(a==b)
        return;
    if(max_change)
        update(true,pos[a] + 1,pos[b],val);
    else
        update(false,pos[a] + 1,pos[b],val);
}

int query(int pos,int v = 1,int start = 1,int end = N)
{
    if(start==end)
    {
        int ret = -1;
        if(lazy_max[v] != -1)
            ret = lazy_max[v];
        if(lazy_min[v] != -1)
            ret = lazy_min[v];
        if(ret==-1)
            ret = 1;
        return ret;
    }
    propagate(v,start,end);
    int mid = (start + end)/2;
    if(pos <= mid)
        return query(pos,2*v,start,mid);
    else
        return query(pos,2*v+1,mid+1,end);
}

int main()
{
    scanf("%d",&N);
    for(int a,b,i = 1 ; i < N ; i++)
    {
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,1);
    decompose(1,1);
    for(int i = 1 ; i <= N ; i++)
    {
        maxim[i] = 1e9;
        minim[i] = -1;
    }
    scanf("%d",&K);
    for(int x,y,z,i = 1 ; i <= N ; i++)
    {
        char op;
        scanf(" %c%d%d%d",&op,&x,&y,&z);
        if(op=='M')
            update_tree(x,y,z,true);
        else
            update_tree(x,y,z,false);
    }
    for(int i = 2 ; i <= N ; i++)
    {
        int val = query(i);
        printf("%d %d %d\n",has_pos[i],par[has_pos[i]],val);
    }
    return 0;
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
minmaxtree.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:154:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
minmaxtree.cpp:158:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         scanf(" %c%d%d%d",&op,&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 113 ms 14672 KB Integer 0 violates the range [1, 70000]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 10836 KB Integer 0 violates the range [1, 68552]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -