QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #241712 | #6312. 城市建造 | w4p3r | Compile Error | / | / | C++20 | 4.6kb | 2023-11-06 16:14:38 | 2023-11-06 16:14:39 |
Judging History
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;
}
Details
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;
| ~~~^~~~~~~~~~~~~