QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#241712#6312. 城市建造w4p3rCompile Error//C++204.6kb2023-11-06 16:14:382023-11-06 16:14:39

Judging History

你现在查看的是最新测评结果

  • [2023-11-06 16:14:39]
  • 评测
查看
  • [2023-11-06 16:14:38]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define db double
#define ve vector<int>
#define pa pair<int,int>
#define fr first
#define sd second
#define pb push_back
#define mp make_pair
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
const int mod = 998244353;
#define N 200010
int n, m, k;
vector<pair<int, int>>e[N];
int ksm(int a, int b)
{
	int ans = 1;
	while (b) {if (b & 1)ans = 1LL * ans * a % mod; b >>= 1; a = 1LL * a * a % mod;}
	return ans;
}
namespace S1
{
vector<int>g[N];
int vst[N], dep[N], s[N];
int sz[N], fa[N];
int vis[N], h[N];
set<int>S;
map<pair<int, int>, bool>ma;
int D, fl;
void dfs(int x, int id)
{
	vst[x] = 1;
	for (auto [y, t] : e[x])if (t != id)
		{
			if (!vst[y]) {dep[y] = dep[x] + 1; fa[y] = x; g[x].push_back(y); dfs(y, t);}
			else if (dep[y] < dep[x])
			{
				s[x] ++;
				s[y] --;
			}
		}
}
void calc(int x)
{
	for (int y : g[x]) {calc(y); s[x] += s[y];}
}
void dfs(int x)
{
	sz[x] = 1;
	for (int y : g[x]) {dfs(y); sz[x] += sz[y];}
	if (sz[x] > D) {fl = 0;}
	if (sz[x] == D && x != 1) {sz[x] = 0; vis[x] = vis[fa[x]] = 1;}
}
void DFS(int x, int id)
{
	for (auto [y, _] : e[x])if (_ != id)
		{
			if (h[y]) {if (id && h[y] != h[x])fl = 0;}
			else {h[y] = h[x]; DFS(y, _);}
		}
}
int ck(int d)
{
	S.clear(); D = d, fl = 1; FOR(i, 1, n)h[i] = vis[i] = 0;
	dfs(1);
	// cout << d << endl;
	// for (int x : S)cout << x << ' '; cout << endl;
	int S = 0;
	FOR(i, 1, n)S += vis[i];
	if (fl == 0 || S != n / d)return 0;
	FOR(x, 1, n)if (vis[x]) h[x] = x;
	FOR(x, 1, n)if (vis[x]) DFS(x, 0);
	return fl;
}
int sol()
{
	dep[1] = 1; dfs(1, 0); int ans = 1; calc(1);
	FOR(d, 2, n)if (n % d == 0 && d < n)
	{
		if (ck(d)) {ans ++;}
	}
	return ans;
}
}
namespace S2
{
vector<int>g[N];
int vst[N], dep[N], s[N];
int dfn[N], low[N], Ti, tlow[N];
int sz[N], fa[N];
int dp[N], sl[N], sr[N];
int SUM, FLAG;
map<pair<int, int>, bool>ma;
int D, fl;
void dfs(int x, int id)
{
	vst[x] = 1; dfn[x] = low[x] = ++ Ti; tlow[x] = n + 1; sz[x] = 1;
	for (auto [y, t] : e[x])if (t != id)
		{
			if (!vst[y]) {dep[y] = dep[x] + 1; fa[y] = x; g[x].push_back(y); dfs(y, t); sz[x] += sz[y]; tlow[x] = min(tlow[x], low[y]); low[x] = min(low[x], low[y]);}
			else if (dep[y] < dep[x])
			{
				low[x] = min(low[x], dfn[y]);
			}
		}
}
void dfs(int x)
{
	int S = 1, num = 1, fl = 0, zero = 0;
	for (int y : g[x])
	{
		dfs(y);
		if (sz[y] < D) {S += sz[y]; if (low[y] < dfn[x])fl = 1;}
		else
		{
			if (dp[y]) {sl[y] = num; num = 1LL * num * dp[y] % mod;}
			else zero ++;
		}
	}
	int m = g[x].size();
	int tmpnum = 1;
	REP(i, m - 1, 0)
	{
		int y = g[x][i];
		if (sz[y] >= D)
		{
			sr[y] = tmpnum;
			tmpnum = 1LL * tmpnum * dp[y] % mod;
		}
	}
	// cout << "EE:" << x << " " << fl << endl;
	if (!fl)
	{
		if ((S == D || S == D + 1) && (!zero))dp[x] = num;
		for (int y : g[x])if (sz[y] >= D && (S + sz[y] == D || S + sz[y] == D + 1))
			{
				if (zero >= 2 || low[y] < dfn[x])continue;
				if (dp[y] && (!zero))dp[x] = (dp[x] + 1LL * sl[y] * sr[y] % mod) % mod;
				else if (!dp[y])dp[x] = (dp[x] + num) % mod;
			}
	}
	if (x == 1)SUM = (SUM + dp[x]) % mod;
	else
	{
		S = n - sz[x] + 1, num = 1, fl = 0, zero = 0;
		for (int y : g[x])
		{
			if (sz[y] < D)S += sz[y];
			else
			{
				if (!dp[y] || low[y] < dfn[x])zero ++;
				else num = 1LL * num * dp[y] % mod;
			}
		}
		if ((S == D || S == D + 1) && (!zero))SUM = (SUM + num) % mod;
	}
}
int calc(int d)
{
	// cout << "START:" << d << endl;
	FOR(i, 1, n)dp[i] = 0;
	FOR(i, 1, n)if (d >= max(20, sqrt(n)) && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
	D = d; SUM = 0; dfs(1);
	return SUM;
}
int sol()
{
	dep[1] = 1; dfs(1, 0); int ans = 0;
	for (int d = 1; d < n - 1; d ++)
	{
		int t = n / d, p = n - d * t;
		if (p <= t)ans = (ans + calc(d)) % mod;
		// cout << "GG:" << ans << endl;
	}
	return ans;
}
}
signed main()
{
	// freopen("14.in", "r", stdin);
	// freopen("my.out", "w", stdout);
	n = read(), m = read(), k = read();
	FOR(i, 1, m)
	{
		int x = read(), y = read();
		e[x].push_back({y, i}); e[y].push_back({x, i});
	}
	if (k == 0)cout << S1 :: sol() << '\n';
	else cout << (S2 :: sol() + mod - S1 :: sol() + 1) % mod << '\n';
	return 0;
}
源文件, 语言: C++20

详细 

answer.code: In function ‘int S2::calc(int)’:
answer.code:176:33: error: no matching function for call to ‘max(int, __gnu_cxx::__enable_if<true, double>::__type)’
  176 |         FOR(i, 1, n)if (d >= max(20, sqrt(n)) && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
      |                              ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
answer.code:176:33: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’})
  176 |         FOR(i, 1, n)if (d >= max(20, sqrt(n)) && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
      |                              ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
answer.code:176:33: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’})
  176 |         FOR(i, 1, n)if (d >= max(20, sqrt(n)) && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
      |                              ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)’
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
answer.code:176:33: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  176 |         FOR(i, 1, n)if (d >= max(20, sqrt(n)) && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
      |                              ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)’
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
answer.code:176:33: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  176 |         FOR(i, 1, n)if (d >= max(20, sqrt(n)) && sz[i] >= d + 2 && sz[i] < 2 * d)return 0;
      |                              ~~~^~~~~~~~~~~~~
English 繁體中文 简体中文

服务器时间: 2024-12-02 23:27:54 | 开源项目