Submission #61697

#	Time	Username	Problem	Language	Result	Execution time	Memory
61697		hamzqq9	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	418 ms	37352 KiB

minmaxtree

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000000000000
#define iii pair<int,pair<int,int> >
#define st first
#define nd second
#define pb push_back
#define umax(x,y) x=max(x,(y))
#define pw(x) (1<<(x))
#define N 70005
#define LOG 21
#define all(x) x.begin(),x.end()
#define sz(x) x.size()

int n,x,y,z,q;
vector<int> v[N],del[N];
multiset<int> add[N];
int cost[N],baba[LOG+2][N],der[N];
vector<iii> Min,Max;

int lca(int x,int y) {

  if(der[x]<der[y]) swap(x,y);

  int dx=der[x];

  for(int i=LOG-1;i>=0;i--) {

    if(dx-pw(i)>=der[y]) {

      x=baba[i][x];
      dx-=pw(i);

    }

  }

  if(x==y) return x;

  for(int i=LOG-1;i>=0;i--) {

    if(baba[i][x]!=baba[i][y]) {

      x=baba[i][x];
      y=baba[i][y];

    }

  }

  return baba[0][x];

}

void dfs3(int node,int ata) {

  for(int i:v[node]) {

    if(i==ata) continue ;

    dfs3(i,node);

    if(sz(add[i])>sz(add[node])) swap(add[i],add[node]);

    for(auto x:add[i]) add[node].insert(x);

    add[i].clear();

  }

  for(int i:del[node]) {

    add[node].erase(add[node].find(i));
    add[node].erase(add[node].find(i));

  }

  if(node==1) return ;

  if(sz(add[node])) cost[node]=*add[node].rbegin();
  else cost[node]=123;

}

void build_lca() {

  for(int i=1;i<LOG;i++) {

    for(int j=1;j<=n;j++) {

      baba[i][j]=baba[i-1][baba[i-1][j]];

    }

  }

}

void dfs1(int node,int ata) {

  baba[0][node]=ata;
  der[node]=der[ata]+1;

  for(int i:v[node]) {

    if(i==ata) continue ;

    dfs1(i,node);

  }

}

int main() {
  
//  freopen("in.txt","r",stdin);

  scanf("%d ",&n);

  for(int i=1;i<n;i++) {

    scanf("%d %d",&x,&y);

    v[x].pb(y);
    v[y].pb(x);

  }

  dfs1(1,0);
  build_lca();

  scanf("%d",&q);

  while(q--) {

    char c;

    scanf(" %c %d %d %d",&c,&x,&y,&z);

    if(c=='M') {

      Max.pb({z,{x,y}});      

    }
    else {

      Min.pb({z,{x,y}});

    }

  }

  sort(all(Max),greater<iii>());
  sort(all(Min));

  if(!sz(Min)) {

    for(auto x:Max) {

      int n1=x.nd.st;
      int n2=x.nd.nd;
      int cst=x.st;

      add[n1].insert(cst);
      add[n2].insert(cst);

      del[lca(n1,n2)].pb(cst);

    }

    dfs3(1,0);

    for(int i=2;i<=n;i++) {

      printf("%d %d %d\n",i,baba[0][i],cost[i]);

    }

    return 0;

  }

  assert(0);

}

Compilation message (stderr)

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d ",&n);
   ~~~~~^~~~~~~~~~
minmaxtree.cpp:123: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:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
minmaxtree.cpp:139:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %c %d %d %d",&c,&x,&y,&z);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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