Submission #168579

#	Time	Username	Problem	Language	Result	Execution time	Memory
168579		m3r8	Min-max tree (BOI18_minmaxtree)	C++14	100 / 100	488 ms	41612 KiB

minmaxtree

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
#include <queue>
#include <string.h>
#include <map>


#define ii std::pair<int,int>
#define INF 1000000010
#define left(i) (i<<1)
#define right(i) ((i<<1)+1)
#define N 70100

typedef struct node{
  int mx,mn;  
}node;

node seg[N*4];
void build(){
  for(int i = 0;i<N*4;i++)seg[i] = {INF,-1};
};

void update(int n, int l, int r, int a, int b, int v, int f){
  if(l >= r)return;  
  if(l >= b || a >= r)return;
  if(a <= l && r <= b){
    if(f)seg[n].mx = std::min(seg[n].mx,v);  
    else seg[n].mn = std::max(seg[n].mn,v);
  }else{
    int m = (l+r)>>1;  
    update(right(n),m,r,a,b,v,f);
    update(left(n),l,m,a,b,v,f);
  };
};

int querry(int n, int l, int r, int x, int f){
  if(l > x || r <= x)return f ? INF : -1; 
  if(l == x && l == r-1)return f ? seg[n].mx : seg[n].mn;
  else{
    int m = (l+r)>>1;  
    int vval;
    if(x >= m){
      vval = querry(right(n),m,r,x,f);
    }else{
      vval = querry(left(n),l,m,x,f); 
    };
    return f ? std::min(seg[n].mx,vval) : std::max(seg[n].mn,vval);
  };
};

int head[N];
std::vector<int> adj[N];
int ppar[N][20];
int in[N];
int out[N];
int cnt = 1;
std::map<int,std::vector<int>> mpp;
std::map<int,ii> rmp;
std::map<int,int> used;
std::map<int,int> gg;
ii tt[N];
int vv[N];
int n;

int dfs(int v,int p){
  ppar[v][0] = p;
  for(int i = 1;i<20;i++){
    ppar[v][i] = ppar[ppar[v][i-1]][i-1];  
  };
  int sz = 1;
  int mx = 0;
  int id = 0;
  for(int i = 0;i<adj[v].size();i++){
    if(adj[v][i] != p){
      int ss = dfs(adj[v][i],v);
      if(ss >mx){
        mx = ss;  
        id = i;
      };
      sz += ss;
    };
  };
  if(mx){
    int tmp = adj[v][0];  
    adj[v][0] = adj[v][id];
    adj[v][id] = tmp;
  };
  return sz;
};

void dff(int v, int p){
  in[v] = cnt++;  
  rmp[in[v]-1] = {p,v};
  for(int i = 0;i<adj[v].size();i++){
    int nxt = adj[v][i];
    if(nxt != p){
      if(!i)head[nxt] = head[v];  
      dff(nxt,v);
    };
  };
  out[v] = cnt;
};

int before(int v, int u){
  if(!u)return false;
  if(!v)return true;  
  return in[v] < in[u] && out[v] >= out[u];
};

int lca(int v, int u){
  if(u == v)return v;
  if(before(v,u))return v;  
  else if(before(u,v))return u;
  for(int i = 19;i>=0;i--){
    if(!before(ppar[v][i],u)){
      v = ppar[v][i];
    };  
  };
  return ppar[v][0];
};

void upp(int s, int e, int v, int f){
  int lc = lca(s,e);
  if(lc != e){
    upp(s,lc,v,f);  
    upp(e,lc,v,f);
  };
  while(s != e){
    int tmp = head[s];  
    if(!before(tmp,e) && tmp != e){
      update(1,0,n,in[tmp],in[s],v,f);
      update(1,0,n,in[tmp]-1,in[tmp],v,f);
      s = ppar[tmp][0];
    }else{
      //printf("hld: %d %d %d\n",s,e,tmp);
      //printf("hld: %d %d %d\n",in[e],in[s],v);
      update(1,0,n,in[e],in[s],v,f);
      break;
    };
  };
};


int main(void){
  for(int i = 0;i<N;i++)head[i] = i;
  build();
  int k;
  scanf("%d",&n);
  int x,y,z;
  char str[2];
  memset(vv,-1,sizeof(vv));
  for(int i = 0;i<n-1;i++){
    scanf("%d %d",&x,&y);  
    adj[x].push_back(y);
    adj[y].push_back(x);
  };
  dfs(1,0);
  dff(1,0);
  scanf("%d",&k);
  //printf("%d\n",k);
  for(int i = 0;i<k;i++){
    scanf("%s %d %d %d",str,&x,&y,&z);
    if(str[0] == 'M'){
      upp(x,y,z,1);
    }else{
      upp(x,y,z,0);
    };
  };
  for(int i = 1;i<n;i++){
    int mnn = querry(1,0,n,i,0);  
    int mxx = querry(1,0,n,i,1);  
    mpp[mnn].push_back(i);
    mpp[mxx].push_back(i);
    //printf("%d %d\n",mnn,mxx);
    tt[i] = {mnn,mxx};
  };
  std::priority_queue<ii,std::vector<ii>,std::greater<ii>> pq;
  for(auto &i : mpp){
    if(i.first != INF && i.first != -1){
      pq.push({i.second.size(),i.first});  
      used[i.first] = i.second.size();
    };
  };
 
  while(pq.size()){
    ii akt = pq.top();pq.pop();  
    if(used[akt.second] == akt.first){
      auto &vec = mpp[akt.second];
      int id = 0;
      while(true){
        id = vec[vec.size()-1];
        vec.pop_back();
        if(vv[id] == -1){
          vv[id] = akt.second; 
          break;
        };
      };
      int mnn = tt[id].first;  
      int mxx = tt[id].second;  
      gg[akt.second] = 1;
      if(akt.second == mnn){
        if(mxx != INF && !gg[mxx]){
          pq.push({--used[mxx],mxx});
        };
      }else{
        if(mnn != -1 && !gg[mnn]){
          pq.push({--used[mnn],mnn});
        };  
      };
    };
  };
  for(int i = 1;i<n;i++){
    ii akt = rmp[i];  
    int cc = vv[i] != -1 ? vv[i] : tt[i].second;
    printf("%d %d %d\n",akt.first,akt.second,cc);
  };
  return 0;
};

Compilation message (stderr)

minmaxtree.cpp: In function 'int dfs(int, int)':
minmaxtree.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<adj[v].size();i++){
                 ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dff(int, int)':
minmaxtree.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<adj[v].size();i++){
                 ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
minmaxtree.cpp:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&x,&y);  
     ~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&k);
   ~~~~~^~~~~~~~~
minmaxtree.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s %d %d %d",str,&x,&y,&z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42