제출 #851491

#제출 시각아이디문제언어결과실행 시간메모리
851491hngwlog철인 이종 경기 (APIO18_duathlon)C++14
36 / 100
70 ms24340 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define _size(x) (int)x.size() #define BIT(i, x) ((x >> i) & 1) #define MASK(n) ((1 << n) - 1) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--) #define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i) #define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i) #define FORALL(i, a) for (auto i: a) #define fastio ios_base::sync_with_stdio(0); cin.tie(0); int n, m; vector<vector<int>> adj; namespace subtask1 { void main() { vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1))); FOR(i, 1, n) { vector<vector<int>> g((1 << n), vector<int>(n)); FORALL(j, adj[i]) { if (j == i) continue; g[(1 << (i - 1)) | (1 << (j - 1))][j - 1] = 1; } FOR(mask, 0, MASK(n)) { FORB1(_mask, mask) { int u = __builtin_ctz(_mask); if (!g[mask][u]) continue; FORB1(__mask, mask) { int v = __builtin_ctz(__mask); if (i == u + 1 || i == v + 1 || u == v) continue; f[i][v + 1][u + 1]++; } FORALL(v, adj[u + 1]) { if (BIT(v - 1, mask)) continue; g[mask | (1 << (v - 1))][v - 1] = 1; } } } } int ans = 0; FOR(i, 1, n) FOR(j, 1, n) FOR(z, 1, n) { if (i == j || i == z || j == z) continue; ans += (f[i][j][z] > 0); } cout << ans << '\n'; } } namespace subtask2 { void main() { } } bool checkSub3() { vector<int> deg(n + 1); FOR(u, 1, n) FORALL(v, adj[u]) deg[v]++; FOR(u, 1, n) if (deg[u] > 2) return false; return true; } namespace subtask3 { const int inf = 1e9; int t_time = 0; vector<int> num, low, child, depth, vtx, sz; vector<vector<int>> p; void dfs(int _p, int u) { vtx.push_back(u); num[u] = ++t_time; low[u] = inf; FORALL(v, adj[u]) { if (v == _p) continue; if (num[v]) low[u] = min(low[u], num[v]); else { depth[v] = depth[u] + 1; p[0][v] = u; dfs(u, v); low[u] = min(low[u], low[v]); child[u] += child[v]; } } } int jump(int u, int l) { FORB1(mask, l) u = p[__builtin_ctz(mask)][u]; return u; } void main() { num.resize(n + 1); low.resize(n + 1); child.assign(n + 1, 1); sz.resize(n + 1); depth.resize(n + 1); p.assign(20, vector<int>(n + 1)); long long ans = 0; FOR(u, 1, n) { if (num[u]) continue; vtx.clear(); dfs(u, u); int cnt = _size(vtx); if (low[u] == inf) ans += 1LL * cnt * (cnt - 1) * (cnt - 2); else ans += 1LL * cnt * (cnt - 1) * (cnt - 2); FORALL(v, vtx) sz[v] = cnt; } FOR(j, 1, 19) FOR(i, 1, n) p[j][i] = p[j - 1][p[j - 1][i]]; vector<int> f(n + 1); FOR(u, 1, n) { if (!p[0][u]) continue; if (low[u] < num[p[0][u]]) f[p[0][u]] += child[u]; } FOR(u, 1, n) { if (low[u] != inf) continue; FORALL(v, adj[u]) { if (depth[u] > depth[v]) { int value = sz[u] - child[u] + f[u]; ans -= 1LL * value * (value - 1); } else { int r = jump(v, depth[u] - depth[v] - 1); int value = child[r]; if (low[r] < num[u]) value += sz[u] - child[u]; ans -= 1LL * value * (value - 1); } } } cout << ans << '\n'; } } vector<int> vis_check; int dfs_check(int p, int u) { int res = 1; vis_check[u]++; FORALL(v, adj[u]) { if (v == p) continue; if (vis_check[v]) return 0; res = min(res, dfs_check(u, v)); } return res; } bool checkSub45() { vis_check.resize(n + 1); int res = 1; FOR(u, 1, n) if (!vis_check[u]) res = min(res, dfs_check(- 1, u)); if (res) return true; return false; } namespace subtask45 { const int inf = 1e9; int t_time = 0; vector<int> num, low, child, depth, vtx, sz; vector<vector<int>> p; void dfs(int _p, int u) { vtx.push_back(u); num[u] = ++t_time; low[u] = inf; FORALL(v, adj[u]) { if (v == _p) continue; if (num[v]) low[u] = min(low[u], num[v]); else { depth[v] = depth[u] + 1; p[0][v] = u; dfs(u, v); low[u] = min(low[u], low[v]); child[u] += child[v]; } } } int jump(int u, int l) { FORB1(mask, l) u = p[__builtin_ctz(mask)][u]; return u; } void main() { num.resize(n + 1); low.resize(n + 1); child.assign(n + 1, 1); sz.resize(n + 1); depth.resize(n + 1); p.assign(20, vector<int>(n + 1)); long long ans = 0; FOR(u, 1, n) { if (num[u]) continue; vtx.clear(); dfs(u, u); int cnt = _size(vtx); ans += 1LL * cnt * (cnt - 1) * (cnt - 2); FORALL(v, vtx) sz[v] = cnt; } FOR(j, 1, 19) FOR(i, 1, n) p[j][i] = p[j - 1][p[j - 1][i]]; vector<int> f(n + 1); FOR(u, 1, n) { if (!p[0][u]) continue; if (low[u] < num[p[0][u]]) f[p[0][u]] += child[u]; } FOR(u, 1, n) { FORALL(v, adj[u]) { if (depth[u] > depth[v]) { int value = sz[u] - child[u] + f[u]; ans -= 1LL * value * (value - 1); } else { int r = jump(v, depth[u] - depth[v] - 1); int value = child[r]; if (low[r] < num[u]) value += sz[u] - child[u]; ans -= 1LL * value * (value - 1); } } } cout << ans << '\n'; } } bool checkSub67() { return true; } namespace subtask67 { const int inf = 1e9; int t_time = 0; vector<int> num, low, child, root, depth, par, tr, a; int getroot(int u) { return root[u] == u ? u : (root[u] = getroot(root[u])); } bool unite(int u, int v) { u = getroot(u), v = getroot(v); if (u == v) return false; root[v] = u; return true; } void dfs(int p, int u) { a[u] = u; num[u] = ++t_time; tr[t_time] = u; low[u] = inf; FORALL(v, adj[u]) { if (v == p) continue; if (num[v]) low[u] = min(low[u], num[v]); else { depth[v] = depth[u] + 1; par[v] = u; dfs(u, v); if (low[v] <= num[u]) a[u] = a[v]; unite(u, v); child[u] += child[v]; low[u] = min(low[u], low[v]); } } } void main() { num.resize(n + 1); low.resize(n + 1); child.assign(n + 1, 1); root.resize(n + 1); FOR(i, 1, n) root[i] = i; a.resize(n + 1); tr.resize(n + 1); depth.resize(n + 1); par.resize(n + 1); FOR(i, 1, n) if (!num[i]) dfs(i, i); long long ans = 0; FOR(c, 1, n) { ans += 1LL * (child[c] - 1) * (child[getroot(c)] - child[c]) * 2; ans += 1LL * (child[c] - 1) * (child[c] - 2); FORALL(u, adj[c]) { if (par[c] == u || par[u] != c) continue; ans -= 1LL * child[u] * (child[u] - 1); if (low[u] > num[c]) continue; int num = depth[a[c]] - depth[c]; ans += 1LL * num * (child[u] - 1) * 2 - 1LL * num * (num - 1); } if (!par[c] || low[c] >= num[c]) continue; int num = depth[c] - depth[tr[low[c]]] - 1; ans += 1LL * num * (child[getroot(c)] - child[c] - 1) * 2 - 1LL * num * (num - 1); } cout << ans << '\n'; } } int main() { fastio; cin >> n >> m; adj.resize(n + 1); REP(i, m) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } FOR(u, 1, n) { sort(adj[u].begin(), adj[u].end()); adj[u].resize(unique(adj[u].begin(), adj[u].end()) - adj[u].begin()); } if (n <= 10 && m <= 100) subtask1::main(); else if (n <= 50 && m <= 100) subtask2::main(); else if (checkSub3()) subtask3::main(); else if (checkSub45()) subtask45::main(); else if (checkSub67()) subtask67::main(); return 0; }

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

count_triplets.cpp: In function 'void subtask1::main()':
count_triplets.cpp:41:35: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   41 |                         if (BIT(v - 1, mask)) continue;
      |                                 ~~^~~
count_triplets.cpp:7:26: note: in definition of macro 'BIT'
    7 | #define BIT(i, x) ((x >> i) & 1)
      |                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...