제출 #244610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244610		TheLorax	Railway (BOI17_railway)	C++11	36 / 100	322 ms	49648 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){
  for(int k=lgn-1; !ancof(lca,b); ) {
    // fprintf(stderr, "%d %d\n", lca, k);
    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 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++){
    int s=SZ(d[i]);
    for(int j=1; j<s; j++){
      int a=d[i][j-1], b=d[i][j];
      // fprintf(stderr, "%d %d\n", a ,b);
      int lca=upd(a,b); upd(b,a);
    }
  }
  fprintf(stderr,"%ld\n", clock());

  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");
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'int main()':
railway.cpp:96:11: warning: unused variable 'lca' [-Wunused-variable]
       int lca=upd(a,b); upd(b,a);
           ^~~
railway.cpp:57: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:69: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:75: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:78: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: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25