제출 #1306335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306335		farica	Cat in a tree (BOI17_catinatree)	C++20	컴파일 에러	0 ms	0 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";

const int MOD = 998244353;
const int INF = 1e9;

template<ll mod>
struct modnum {
	static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

	using S = conditional_t<is_big_mod, ll, int>;
	using L = conditional_t<is_big_mod, __int128, ll>;

	S x;

	modnum() : x(0) {}
	modnum(ll _x) {
		_x %= static_cast<ll>(mod);
		if (_x < 0) { _x += mod; }
		x = _x;
	}

	modnum pow(ll n) const {
		modnum res = 1;
		modnum cur = *this;
		while (n > 0) {
			if (n & 1) res *= cur;
			cur *= cur;
						n /= 2;
		}
		return res;
	}
	modnum inv() const { return (*this).pow(mod-2); }

	modnum& operator+=(const modnum& a){
		x += a.x;
		if (x >= mod) x -= mod;
		return *this;
	}
	modnum& operator-=(const modnum& a){
		if (x < a.x) x += mod;
		x -= a.x;
		return *this;
	}
	modnum& operator*=(const modnum& a){
		x = static_cast<L>(x) * a.x % mod;
		return *this;
	}
	modnum& operator/=(const modnum& a){ return *this *= a.inv(); }

	friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
	friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
	friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
	friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }

	friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
	friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
	friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

	friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
	friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;

	vector<T> segtree;
	int len;

  public:
	SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}

	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1];
		}
	}

	T range_sum(int start, int end) {
		T sum = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { sum += segtree[start++]; }
			if (end % 2 == 1) { sum += segtree[--end]; }
		}
		return sum;
	}
};

struct BIT {
  vector<ll>b;
  int n;

  void init(int _n) {
	n = _n ;
	b.assign(n+1, 0);
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, ll v) {
	  ++x;
	for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  ll query(int x) {
	ll ans = 0;
	++x;
	for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
	return ans;
  }
} bit;

int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

int inv_ecd(int a, int m) {
	int x, y;
	int g = gcd(a, m, x, y);
	if(g != 1) return -1;
	x = (x + m) % m;
	return x;
}
void solve() {
	int n, d;
	cin >> n >> d;
	vi p(n), ch(n, 0);
	for(int i=1; i<n; ++i) {
		cin >> p[i];
		++ch[p[i]];
	}
	if(d > n) {
		cout << 1 << endl;
		return;
	}
	vector<vi>dp(n, vi(n+1, 0));
	queue<int>q;
	for(int i=0; i<n; ++i) if(!ch[i]) q.push(i);
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		dp[cur][0] = max(dp[cur][0], 1);
		if(!cur) break;
		for(int i=1; i<=n; ++i) {
			if(i>=d) dp[p[cur]][0] += dp[cur][i];
			dp[p[cur]][i] += dp[cur][i-1];
		}
		--ch[p[cur]];
		if(!ch[p[cur]]) q.push(p[cur]);
	}
	int ans = 1;
	for(int i=0; i<=n; ++i) ans = max(ans, dp[0][i]);
	cout << ans << endl;
} 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int tc = 1;
	while(tc--) {
		solve();
	}

}
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";

const int MOD = 998244353;
const int INF = 1e9;

template<ll mod>
struct modnum {
	static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

	using S = conditional_t<is_big_mod, ll, int>;
	using L = conditional_t<is_big_mod, __int128, ll>;

	S x;

	modnum() : x(0) {}
	modnum(ll _x) {
		_x %= static_cast<ll>(mod);
		if (_x < 0) { _x += mod; }
		x = _x;
	}

	modnum pow(ll n) const {
		modnum res = 1;
		modnum cur = *this;
		while (n > 0) {
			if (n & 1) res *= cur;
			cur *= cur;
						n /= 2;
		}
		return res;
	}
	modnum inv() const { return (*this).pow(mod-2); }

	modnum& operator+=(const modnum& a){
		x += a.x;
		if (x >= mod) x -= mod;
		return *this;
	}
	modnum& operator-=(const modnum& a){
		if (x < a.x) x += mod;
		x -= a.x;
		return *this;
	}
	modnum& operator*=(const modnum& a){
		x = static_cast<L>(x) * a.x % mod;
		return *this;
	}
	modnum& operator/=(const modnum& a){ return *this *= a.inv(); }

	friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
	friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
	friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
	friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }

	friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
	friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
	friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

	friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
	friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;

	vector<T> segtree;
	int len;

  public:
	SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}

	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1];
		}
	}

	T range_sum(int start, int end) {
		T sum = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { sum += segtree[start++]; }
			if (end % 2 == 1) { sum += segtree[--end]; }
		}
		return sum;
	}
};

struct BIT {
  vector<ll>b;
  int n;

  void init(int _n) {
	n = _n ;
	b.assign(n+1, 0);
  }
  inline int lowbit(int x) { return x & (-x); }
  void update(int x, ll v) {
	  ++x;
	for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  ll query(int x) {
	ll ans = 0;
	++x;
	for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
	return ans;
  }
} bit;

int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

int inv_ecd(int a, int m) {
	int x, y;
	int g = gcd(a, m, x, y);
	if(g != 1) return -1;
	x = (x + m) % m;
	return x;
}
void solve() {
	int n, d;
	cin >> n >> d;
	vi p(n), ch(n, 0);
	for(int i=1; i<n; ++i) {
		cin >> p[i];
		++ch[p[i]];
	}
	if(d > n) {
		cout << 1 << endl;
		return;
	}
	vector<vi>dp(n, vi(n+1, 0));
	queue<int>q;
	for(int i=0; i<n; ++i) if(!ch[i]) q.push(i);
	while(!q.empty()) {
		int cur = q.front();
		q.pop();
		dp[cur][0] = max(dp[cur][0], 1);
		if(!cur) break;
		for(int i=1; i<=n; ++i) {
			if(i>=d) dp[p[cur]][0] += dp[cur][i];
			dp[p[cur]][i] += dp[cur][i-1];
		}
		--ch[p[cur]];
		if(!ch[p[cur]]) q.push(p[cur]);
	}
	int ans = 1;
	for(int i=0; i<=n; ++i) ans = max(ans, dp[0][i]);
	cout << ans << endl;
} 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int tc = 1;
	while(tc--) {
		solve();
	}

}

컴파일 시 표준 에러 (stderr) 메시지

catinatree.cpp:189:11: error: redefinition of 'const int MOD'
  189 | const int MOD = 998244353;
      |           ^~~
catinatree.cpp:9:11: note: 'const int MOD' previously defined here
    9 | const int MOD = 998244353;
      |           ^~~
catinatree.cpp:190:11: error: redefinition of 'const int INF'
  190 | const int INF = 1e9;
      |           ^~~
catinatree.cpp:10:11: note: 'const int INF' previously defined here
   10 | const int INF = 1e9;
      |           ^~~
catinatree.cpp:193:8: error: redefinition of 'struct modnum<mod>'
  193 | struct modnum {
      |        ^~~~~~
catinatree.cpp:13:8: note: previous definition of 'struct modnum<mod>'
   13 | struct modnum {
      |        ^~~~~~
catinatree.cpp:251:26: error: redefinition of 'class SumSegmentTree<T>'
  251 | template <class T> class SumSegmentTree {
      |                          ^~~~~~~~~~~~~~
catinatree.cpp:71:26: note: previous definition of 'class SumSegmentTree<T>'
   71 | template <class T> class SumSegmentTree {
      |                          ^~~~~~~~~~~~~~
catinatree.cpp:279:8: error: redefinition of 'struct BIT'
  279 | struct BIT {
      |        ^~~
catinatree.cpp:99:8: note: previous definition of 'struct BIT'
   99 | struct BIT {
      |        ^~~
catinatree.cpp:298:3: error: conflicting declaration 'int bit'
  298 | } bit;
      |   ^~~
catinatree.cpp:118:3: note: previous declaration as 'BIT bit'
  118 | } bit;
      |   ^~~
catinatree.cpp:300:5: error: redefinition of 'int gcd(int, int, int&, int&)'
  300 | int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1
      |     ^~~
catinatree.cpp:120:5: note: 'int gcd(int, int, int&, int&)' previously defined here
  120 | int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1
      |     ^~~
catinatree.cpp:312:5: error: redefinition of 'int inv_ecd(int, int)'
  312 | int inv_ecd(int a, int m) {
      |     ^~~~~~~
catinatree.cpp:132:5: note: 'int inv_ecd(int, int)' previously defined here
  132 | int inv_ecd(int a, int m) {
      |     ^~~~~~~
catinatree.cpp:319:6: error: redefinition of 'void solve()'
  319 | void solve() {
      |      ^~~~~
catinatree.cpp:139:6: note: 'void solve()' previously defined here
  139 | void solve() {
      |      ^~~~~
catinatree.cpp:351:5: error: redefinition of 'int main()'
  351 | int main(){
      |     ^~~~
catinatree.cpp:171:5: note: 'int main()' previously defined here
  171 | int main(){
      |     ^~~~