제출 #546850

#제출 시각아이디문제언어결과실행 시간메모리
546850Monarchuwu철인 이종 경기 (APIO18_duathlon)C++17
66 / 100
123 ms26336 KiB
#include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<pii, int> ppi; #define ff first #define ss second const int N = 1e5 + 9; int n, m; vector<int> g[N]; // bridge tree (WA for subtask 89) namespace subtask34567 { int num[N], low[N], tme; int lab[N], cnt_scc, sz[N]; int path[N], top; void tarjan(int u, int p) { num[u] = low[u] = ++tme; path[++top] = u; for (int v : g[u]) if (v != p) { if (num[v]) low[u] = min(low[u], num[v]); else { tarjan(v, u); low[u] = min(low[u], low[v]); } } if (num[u] == low[u]) { // chot ++cnt_scc; int v; do { v = path[top--]; num[v] = low[v] = N; lab[v] = cnt_scc; ++sz[cnt_scc]; } while (v != u); } } vector<ppi> g2[N]; void init_graph() { for (int u = 1; u <= n; ++u) for (int v : g[u]) if (lab[u] != lab[v]) g2[lab[u]].emplace_back(pii(u, v), lab[v]); } ll ans, dp[N][3]; bool vis[N]; void dfs(int u, int p, int vertex) { vis[u] = true; sort(g2[u].begin(), g2[u].end()); /* sort(g2[u].begin(), g2[u].end(), [=](const ppi &a, const ppi &b) { if (a.ff.ff == vertex && b.ff.ff == vertex) return false; if (a.ff.ff == vertex) return true; if (b.ff.ff == vertex) return false; return a.ff < b.ff; }); */ dp[u][1] = sz[u]; dp[u][2] = (ll)(sz[u] - 1) * (sz[u] - 1); ans += (ll)sz[u] * (sz[u] - 1) * (sz[u] - 2); ll cnt(0), dp1(0), dp2(0); int pre(0); for (ppi x : g2[u]) if (x.ss != p) { int v = x.ss; if (pre != x.ff.ff) { dp[u][2] += cnt, cnt = 0; pre = x.ff.ff; } dfs(v, u, x.ff.ss); ans += dp[u][1] * dp[v][2] * 2; ans += dp[u][2] * dp[v][1] * 2; dp[u][1] += dp[v][1]; dp[u][2] += dp[v][2]; dp[u][2] += dp[v][1]; if (vertex != x.ff.ff) { cnt += dp[v][1] * (sz[u] - 1); ans += dp1 * dp[v][1] * 2; } else dp1 += dp[v][1] * (sz[u] - 1); } dp[u][2] += cnt; } void solve() { for (int i = 1; i <= n; ++i) if (!num[i]) tarjan(i, 0); init_graph(); dfs(4, 0, 0); for (int u = 1; u <= cnt_scc; ++u) if (!vis[u]) dfs(u, 0, 0); cout << ans << '\n'; } } bool f[N]; int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m; for (int i = 0, u, v; i < m; ++i) { cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } subtask34567::solve(); } /** /\_/\ * (= ._.) * / >0 \>1 **/ /* ==================================================+ INPUT: | --------------------------------------------------| 15 19 1 2 2 3 3 1 4 5 5 6 6 4 7 8 8 9 9 7 10 11 11 12 12 10 13 14 14 15 15 13 1 10 1 4 1 7 2 13 --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| 726 --------------------------------------------------| ==================================================+ */

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

count_triplets.cpp: In function 'void subtask34567::dfs(int, int, int)':
count_triplets.cpp:67:28: warning: unused variable 'dp2' [-Wunused-variable]
   67 |         ll cnt(0), dp1(0), dp2(0);
      |                            ^~~
#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...