Submission #701942

#	Time	Username	Problem	Language	Result	Execution time	Memory
701942		deadboy	Railway (BOI17_railway)	C++14	100 / 100	305 ms	47608 KiB

railway

// :)

#include <bits/stdc++.h>
     
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
     
     
//-----------------debug--------------------------
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#define deb(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
 
 
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}
 
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = c.begin(); it != c.end(); ++it)
    os << &", "[2 * (it == c.begin())] << *it;
  return os << ']';
}
//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
  (MACRO, ##__VA_ARGS__)
//Change output format here
#define out(x) #x " = " << x << "; "
#define debug(...)                                                              \
  cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << endl
//----------------------------------------------
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define FIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define no cout << "NO\n"; return;
#define yes cout << "YES\n"; return;
#define SP fixed << setprecision(10)
     
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
     
const ll mod = 1e9+7;
const ll oo = 1e18;
const ll N = 1e5*2 + 10, N2 = 1e6;
ll n, m, k, ans;

vector<ll> g[N];
ll cnt[N], re[N], sz[N], mx[N], a[N];

vector<ll> t[N];
void get_sz(ll v, ll fa){
  sz[v]=t[v].size()+1;
  for(auto u : g[v]){
    if(u==fa) continue;
    get_sz(u, v); sz[v]+=sz[u];
  }
}
void cle(ll v, ll fa){
  for(auto c:t[v])
    cnt[c]=0;
  for(auto u : g[v])
    if(u!=fa) cle(u, v);
}
ll sum = 0;
void add(ll c){
  cnt[c]++;
  if(cnt[c]==1) sum++;
  if(cnt[c]==mx[c]) sum--;
}
void ade(ll v, ll fa){
  for(auto c : t[v])
    add(c);
  for(auto u : g[v])
    if(u!=fa) ade(u, v);
}
map<pll, ll> dd;
void dfs(ll v, ll fa, ll tt = 0){
  sum = 0;
  
  pll mx = {0, -1};
  for(auto u : g[v]) if(u!=fa)
    mx = max(mx, {sz[u], u});
  for(auto u : g[v])
    if(u!=mx.ss && u!=fa) dfs(u, v);

  if(mx.ss != -1) dfs(mx.ss, v, 1);
  for(auto c:t[v])
    add(c);
  for(auto u : g[v])
    if(u!=mx.ss && u!=fa) ade(u, v);

  dd[mp(v, fa)]=sum;

  if(tt==0){ 
    cle(v, fa);
    sum = 0;
  }
}
vector<pll> ms;
void code(){
  get_sz(1, 1);
  dfs(1, 1, 1);
  vector<ll> ans;
  for(int i = 0; i < ms.size(); i++){
    ll su = dd[mp(ms[i].ff, ms[i].ss)];
    su += dd[mp(ms[i].ss, ms[i].ff)];
    if(su >= k) ans.pb(i+1);
  }
  cout<< ans.size()<<"\n";
  for(auto u : ans) cout<< u<<" ";
}
int main(){
  FIO;
  cin>> n>> m>> k;
  for(int i = 1; i < n; i++){
    ll v, u; cin>> v>> u;
    g[v].pb(u); g[u].pb(v);
    ms.pb({v,u}) ;
  }
  for(int i = 1; i <= m; i++){
    ll si; cin>> si;
    mx[i] = si;
    while(si--){
      ll x; cin>> x;
      t[x].pb(i);
    }
  }
  code();
} 

Compilation message (stderr)

railway.cpp: In function 'void code()':
railway.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int i = 0; i < ms.size(); i++){
      |                  ~~^~~~~~~~~~~

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