Submission #827339

#	Time	Username	Problem	Language	Result	Execution time	Memory
827339		beaconmc	Railway (BOI17_railway)	C++14	100 / 100	347 ms	45928 KiB

railway

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)



vector<ll> edges[100001];
ll par[100001];
ll depth[100001];
ll pos[100001];
ll ancestor[100001][20];
ll timer = 1;

ll anc(ll a, ll x){
  if (depth[a] <= (1<<x)) return 1;
  if (ancestor[a][x] != -2) return ancestor[a][x];

  if (x==0) ancestor[a][x] = par[a];
  else ancestor[a][x] = anc(anc(a,x-1),x-1);

  return ancestor[a][x];
}

void dfs(ll a, ll p, ll d){
  pos[a] = timer++;
  depth[a] = d;
  par[a] = p;
  for (auto&i : edges[a]){
    if (i != p) dfs(i, a, d+1);
  }
}

ll lca(ll a, ll b){
  if (depth[b] >= depth[a]) swap(a,b);


  FORNEG(i,19,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i);

  if (a==b) return a;


  FORNEG(i,19,-1) if (anc(a, i) != anc(b, i)) a = anc(a,i), b = anc(b,i);

  return par[a];
}

map<pair<ll, ll>, ll> rails;

ll rail[100001];
ll vals[100001];


void calc(ll a, ll p){

  for (auto&i : edges[a]){
    if (i != p){
      calc(i, a);
      ll c,d;
      c = min(a, i);
      d = max(a, i);
      vals[rails[make_pair(c,d)]] += rail[i];
      rail[a] += rail[i];
    }
  }
}


int main(){
  FOR(i,0,100001) FOR(j,0,20) ancestor[i][j] = -2;
  FOR(i,0,100001) rail[i] = 0, vals[i] = 0;

  ll n,m,k;
  cin >> n >> m >> k;
  FOR(i,0,n-1){
    ll a,b;
    cin >> a >> b;
    edges[b].push_back(a);
    edges[a].push_back(b);
    if (a>b) swap(a,b);
    rails[make_pair(a,b)] = i+1;
  }
  dfs(1, -1, 0);

  FOR(i,0,m){
    ll a;
    cin >> a;
    vector<vector<ll>> temp;
    FOR(i,0,a){
      ll tempy; cin >> tempy;
      temp.push_back({pos[tempy], tempy});
    }
    sort(temp.begin(), temp.end());

    FOR(i,0,a-1){
      rail[temp[i][1]] += 1;
      rail[temp[i+1][1]] += 1;
      rail[(lca(temp[i][1], temp[i+1][1]))] -= 2;
    }
    rail[temp[0][1]] += 1;
    rail[temp[a-1][1]] += 1;
    rail[(lca(temp[0][1], temp[a-1][1]))] -= 2;
  }

  calc(1, -1);
  vector<ll> ans;

  FOR(i,1,n){

    if (vals[i] >= 2*k) ans.push_back(i);

  }
  cout << ans.size() << "\n";
  for (auto&i : ans) cout << i << endl;





}

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