Submission #1087540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087540		veehj	September (APIO24_september)	C++17	100 / 100	148 ms	16580 KiB

september

// #include "september.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
vector<int> vist, nchild, pa;
set<int> call, tagged;
vector<vector<int>> child;

void pop(int nw){
  if(nchild[nw]!=0 || nw==0 || !tagged.count(nw)) return;
  tagged.erase(nw);
  nchild[pa[nw]]--;
  pop(pa[nw]);
}

int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
  int ans=0;
  pa=f;
  vist.assign(n, 0);
  nchild.assign(n, 0);
  call={}; tagged={};
  child.assign(n, vector<int>(0));
  for(int i=1; i<n; i++){
    child[pa[i]].pb(i);
    nchild[pa[i]]++;
  }
  for(int i=0; i<n-1; i++){
    for(int j=0; j<m; j++){
      vist[s[j][i]]++;
      if(vist[s[j][i]]!=m){ call.insert(s[j][i]); continue; }
      call.erase(s[j][i]);
	  tagged.insert(s[j][i]);
      if(nchild[s[j][i]]==0) pop(s[j][i]);
    }
    ans+=(tagged.empty() && call.empty());
  }
  return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16