Submission #244673

#	Time	Username	Problem	Language	Result	Execution time	Memory
244673		TheLorax	Railway (BOI17_railway)	C++11	100 / 100	374 ms	49720 KiB

railway

#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;


std::vector<std::vector<ii> > e,p;
std::vector<std::vector<int> > d;
std::vector<ii> so;
ll n, m, k;
int lgn=0, cnt=0;

void rek(int a, int f){
  p[a][0].F=f;
  so[a].F=cnt++;
  for(auto x: e[a])
    if(x.F!=f)
      rek(x.F, a);
  so[a].S=cnt++;
}

bool ancof(int a, int x){
  if(a==-1 || x==-1)
    return false;
  return so[a].F<=so[x].F && so[x].S<=so[a].S;
}

int upd(int lca, int b){
  // fprintf(stderr, "%d %d\n", lca, b);
  for(int k=lgn-1; !ancof(lca,b); ) {
    while(k>0 && (p[lca][k].F==-1 || ancof(p[lca][k].F, b)))
      k--;
    p[lca][k].S++;
    lca=p[lca][k].F;
  }
  return lca;
}

int lca(int lca, int b){
  for(int k=lgn-1; !ancof(lca,b); ) {
    while(k>0 && (p[lca][k].F==-1 || ancof(p[lca][k].F, b)))
      k--;
    lca=p[lca][k].F;
  }
  return lca;
}

int main(){
  scanf("%lld %lld %lld", &n, &m, &k);
  while ((1<<lgn)<n)
    lgn++;
  p.resize(n);
  for(int i=0; i<n; i++)
    p[i].resize(lgn,{-1,0});
  e.resize(n);
  d.resize(m);
  so.resize(n);
  // fprintf(stderr,"%ld\n", clock());

  for(int i=0; i<n-1; i++){
    int a, b; scanf("%d %d", &a, &b);
    a--; b--;
    e[a].PB({b,i+1});
    e[b].PB({a,i+1});
  }
  for(int i=0; i<m; i++){
    int s; scanf("%d", &s);
    d[i].resize(s);
    for(int j=0; j<s; j++){
      scanf("%d", &d[i][j]);
      d[i][j]--;
    }
  }
  // fprintf(stderr,"%ld\n", clock());
  rek(0,-1);
  // fprintf(stderr,"%ld\n", clock());
  for(int j=1; j<lgn; j++)
    for(int i=0; i<n; i++)
      if(p[i][j-1].F!=-1)
        p[i][j].F=p[p[i][j-1].F][j-1].F;
  // fprintf(stderr,"%ld\n", clock());

  for(int i=0; i<m; i++){
    sort(ALL(d[i]),[&](int a, int b){
      return so[a].F<so[b].F;
    });
    int s=SZ(d[i]);
    std::vector<int> st;
    st.PB(d[i][0]);
    for(int j=1; j<s; j++){
      if(ancof(st.back(),d[i][j])){
        upd(d[i][j],st.back());
        if(SZ(st)>1 && ancof(st[SZ(st)-2],st.back()))
          st.pop_back();
      } else{
        int a=st.back();
        st.pop_back();
        if(!st.empty() && !ancof(st.back(),d[i][j])){
          a=st.back();
          st.pop_back();
        }
        if(st.empty())
          st.PB(upd(a,d[i][j]));

        upd(d[i][j],a);
      }
      st.PB(d[i][j]);
    }
  }

  for(int j=lgn-1; j>0; j--)
    for(int i=0; i<n; i++)
      if(p[i][j].F!=-1){
        p[i][j-1].S+=p[i][j].S;
        p[p[i][j-1].F][j-1].S+=p[i][j].S;
      }
  std::vector<int> out;
  for(int i=1; i<n; i++){
    if(p[i][0].S>=k)
      for(auto x: e[i])
        if(x.F==p[i][0].F){
          out.PB(x.S);
          break;
        }
  }
  sort(ALL(out));
  printf("%d\n", SZ(out));
  for(int i: out)
    printf("%d ", i);
  printf("\n");
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", &n, &m, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:78:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int a, b; scanf("%d %d", &a, &b);
               ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:84:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int s; scanf("%d", &s);
            ~~~~~^~~~~~~~~~
railway.cpp:87:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &d[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25