Submission #245198

#	Time	Username	Problem	Language	Result	Execution time	Memory
245198		m3r8	Railway (BOI17_railway)	C++14	100 / 100	299 ms	49756 KiB

railway

#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>


#define N 100100

std::vector<int> adj[N];
std::vector<int> lll[N];
int num[N];
int sst[N];
std::vector<int> erg;
std::set<int> avi[N];
std::vector<int> st[N];
std::vector<int> en[N];

int cnt = 1;
int k;
int in[N];
int out[N];
int pre[N][20];

int bef(int v, int u){
  if(v == 0)return 1;
  if(u == 0)return 0;
  return in[u] >= in[v] && out[u] <= out[v];
};

int lca(int v, int u){
  if(v == u)return v;
  if(bef(v,u))return v;  
  if(bef(u,v))return u;  
  int akt = v;

  for(int i = 19;i>=0;i--){
    if(!bef(pre[akt][i],u)){
      akt = pre[akt][i];  
    };
  };
  return pre[akt][0];
};

void dfs(int v, int p){
  in[v] = cnt++;
  pre[v][0] = p;
  for(int i = 1;i<20;i++){
    pre[v][i] = pre[pre[v][i-1]][i-1];  
  };

  for(int i = 0;i<adj[v].size();i++){
    int u = adj[v][i];
    if(u != p){
      dfs(u,v);
    }else{
      num[v] = lll[v][i];
    };  
  };
  out[v] = cnt-1;
};

void solve(int v, int p){
  int mx = 0;
  int mxi = 0;
  for(int i = 0;i<adj[v].size();i++){
    int u = adj[v][i];  
    if(u != p){
      solve(u,v);  
      if(avi[sst[u]].size() >= mx){
        mx = avi[sst[u]].size();  
        mxi = i;
      };
    };
  };
  sst[v] = v;
  if(adj[v].size() > 1)sst[v] = sst[adj[v][mxi]];
  for(int i = 0;i<adj[v].size();i++){
    int u = adj[v][i];  
    if(u != p){
      if(sst[u] != sst[v]){
        for(auto tmp: avi[sst[u]]){
          avi[sst[v]].insert(tmp);  
        };
      };  
    };
  };
  for(auto i: st[v]){
    avi[sst[v]].insert(i);  
  };
  for(auto i: en[v])avi[sst[v]].erase(i);
  if(avi[sst[v]].size() >= k){
    erg.push_back(num[v]);  
  };
  for(auto i: adj[v]){
    if(i != p && sst[i] != sst[v])avi[sst[i]].clear();  
  };
};

int main(void){
  int n,m;  
  scanf("%d %d %d",&n,&m,&k);
  int a,b;
  for(int i = 1;i<n;i++){
    scanf("%d %d",&a,&b);  
    adj[a].push_back(b);
    adj[b].push_back(a);
    lll[a].push_back(i);
    lll[b].push_back(i);
  };
  dfs(1,0);
  for(int i = 1;i<=m;i++){
    int cc;  
    int s;
    scanf("%d",&cc);
    int lcs = 0;
    for(int j = 0;j<cc;j++){
      scanf("%d",&s);  
      st[s].push_back(i);
      if(!lcs)lcs = s;
      else lcs = lca(lcs,s);
    };
    en[lcs].push_back(i);
  };
  /*
  for(int i = 1;i<=n;i++){
    printf("start %d: ",i);
    for(auto j: st[i])printf("%d ",j);  
    puts("");
    printf("end %d: ",i);
    for(auto j: en[i])printf("%d ",j);  
    puts("");
  };
  */
  solve(1,0);
  printf("%d\n",erg.size());
  std::sort(erg.begin(),erg.end());
  for(int i = 0;i<erg.size();i++){
    printf("%d ",erg[i]);  
  };
  puts("");
  return 0;
};

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<adj[v].size();i++){
                 ~^~~~~~~~~~~~~~
railway.cpp: In function 'void solve(int, int)':
railway.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<adj[v].size();i++){
                 ~^~~~~~~~~~~~~~
railway.cpp:69:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(avi[sst[u]].size() >= mx){
          ~~~~~~~~~~~~~~~~~~~^~~~~
railway.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<adj[v].size();i++){
                 ~^~~~~~~~~~~~~~
railway.cpp:91:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(avi[sst[v]].size() >= k){
      ~~~~~~~~~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:135:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",erg.size());
                 ~~~~~~~~~~^
railway.cpp:137:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<erg.size();i++){
                 ~^~~~~~~~~~~
railway.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&n,&m,&k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);  
     ~~~~~^~~~~~~~~~~~~~~
railway.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&cc);
     ~~~~~^~~~~~~~~~
railway.cpp:117:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&s);  
       ~~~~~^~~~~~~~~

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