oj.uz

Submission #244610

# Submission time Handle Problem Language Result Execution time Memory
244610 2020-07-04T12:13:50 Z TheLorax Railway (BOI17_railway) C++11
36 / 100
 322 ms 49648 KB 
#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");
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 13 ms 3968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 13 ms 3968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 49648 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 321 ms 49268 KB Output is correct
4 Correct 239 ms 48888 KB Output is correct
5 Correct 271 ms 47476 KB Output is correct
6 Correct 220 ms 47988 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 46712 KB Output is correct
2 Correct 173 ms 44664 KB Output is correct
3 Correct 159 ms 44460 KB Output is correct
4 Correct 158 ms 44536 KB Output is correct
5 Correct 160 ms 44536 KB Output is correct
6 Correct 172 ms 46968 KB Output is correct
7 Correct 206 ms 46840 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 46712 KB Output is correct
2 Correct 173 ms 44664 KB Output is correct
3 Correct 159 ms 44460 KB Output is correct
4 Correct 158 ms 44536 KB Output is correct
5 Correct 160 ms 44536 KB Output is correct
6 Correct 172 ms 46968 KB Output is correct
7 Correct 206 ms 46840 KB Output is correct
8 Incorrect 215 ms 45688 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 13 ms 3968 KB Output isn't correct
3 Halted 0 ms 0 KB -