# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
402723 |
2021-05-12T09:50:23 Z |
dxz05 |
Duathlon (APIO18_duathlon) |
C++14 |
|
902 ms |
1048580 KB |
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << "[" << H << "]";
debug_out(T...);
}
#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()
clock_t startTime;
double getCurrentTime() {
return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}
typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 2222;
int n, m;
vector<int> g[N];
int cnt = 0, color[N];
bool cycle = false;
void dfs(int v, int p){
color[v] = 1;
cnt++;
for (int u : g[v]){
if (u == p) continue;
if (color[u] == 1) cycle = true;
if (color[u] == 0) dfs(u, v);
}
color[v] = 2;
}
void Subtask_3(){
ll ans = 0;
for (int i = 1; i <= n; i++){
if (color[i] == 0){
cnt = 0;
cycle = false;
dfs(i, 0);
ans += 1ll * cnt * (cnt - 1) * (cnt - 2) / (cycle ? 1 : 3);
}
}
cout << ans;
exit(0);
}
ll ans5 = 0;
int subtree[N];
bool used[N];
void dfs2(int v, int p){
used[v] = true;
subtree[v] = 1;
for (int u : g[v]){
if (u != p){
dfs2(u, v);
subtree[v] += subtree[u];
}
}
for (int u : g[v]){
if (u != p){
ll x = subtree[u], y = cnt - subtree[u] - 1;
ans5 += x * y;
} else {
ll x = subtree[v] - 1, y = cnt - x - 1;
ans5 += x * y;
}
}
}
void Subtask_5(){
for (int i = 1; i <= n; i++){
if (!used[i]){
cnt = 0;
dfs(i, i);
dfs2(i, i);
}
}
cout << ans5 << endl;
exit(0);
}
void solve(int TC) {
cin >> n >> m;
bool ok3 = true;
while (m--) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
ok3 &= g[u].size() <= 2;
ok3 &= g[v].size() <= 2;
}
if (ok3){
Subtask_3();
}
Subtask_5();
}
int main() {
startTime = clock();
cin.tie(nullptr); cout.tie(nullptr);
ios_base::sync_with_stdio(false);
bool llololcal = false;
#ifdef dddxxz
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
llololcal = true;
#endif
int TC = 1;
// cin >> TC;
for (int test = 1; test <= TC; test++) {
//debug(test);
//cout << "Case #" << test << ": ";
solve(test);
}
if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
530 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
530 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
30504 KB |
Output is correct |
2 |
Correct |
75 ms |
30600 KB |
Output is correct |
3 |
Correct |
66 ms |
28952 KB |
Output is correct |
4 |
Correct |
62 ms |
29708 KB |
Output is correct |
5 |
Correct |
65 ms |
28336 KB |
Output is correct |
6 |
Correct |
68 ms |
28412 KB |
Output is correct |
7 |
Correct |
73 ms |
27920 KB |
Output is correct |
8 |
Correct |
68 ms |
28228 KB |
Output is correct |
9 |
Correct |
60 ms |
27664 KB |
Output is correct |
10 |
Correct |
60 ms |
27876 KB |
Output is correct |
11 |
Correct |
54 ms |
27240 KB |
Output is correct |
12 |
Correct |
73 ms |
27108 KB |
Output is correct |
13 |
Correct |
68 ms |
27148 KB |
Output is correct |
14 |
Correct |
50 ms |
27020 KB |
Output is correct |
15 |
Correct |
40 ms |
26652 KB |
Output is correct |
16 |
Correct |
40 ms |
26572 KB |
Output is correct |
17 |
Correct |
16 ms |
24152 KB |
Output is correct |
18 |
Correct |
15 ms |
24228 KB |
Output is correct |
19 |
Correct |
15 ms |
24160 KB |
Output is correct |
20 |
Correct |
15 ms |
24208 KB |
Output is correct |
21 |
Correct |
15 ms |
24140 KB |
Output is correct |
22 |
Correct |
15 ms |
24192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23756 KB |
Output is correct |
2 |
Correct |
15 ms |
23784 KB |
Output is correct |
3 |
Correct |
15 ms |
23800 KB |
Output is correct |
4 |
Correct |
15 ms |
23756 KB |
Output is correct |
5 |
Correct |
15 ms |
23872 KB |
Output is correct |
6 |
Correct |
15 ms |
23884 KB |
Output is correct |
7 |
Correct |
15 ms |
23840 KB |
Output is correct |
8 |
Correct |
15 ms |
23884 KB |
Output is correct |
9 |
Correct |
15 ms |
23784 KB |
Output is correct |
10 |
Correct |
16 ms |
23756 KB |
Output is correct |
11 |
Correct |
15 ms |
23816 KB |
Output is correct |
12 |
Correct |
15 ms |
23884 KB |
Output is correct |
13 |
Correct |
15 ms |
23756 KB |
Output is correct |
14 |
Correct |
15 ms |
23816 KB |
Output is correct |
15 |
Correct |
16 ms |
23784 KB |
Output is correct |
16 |
Correct |
15 ms |
23872 KB |
Output is correct |
17 |
Correct |
15 ms |
23864 KB |
Output is correct |
18 |
Correct |
15 ms |
23884 KB |
Output is correct |
19 |
Correct |
17 ms |
23772 KB |
Output is correct |
20 |
Correct |
15 ms |
23816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
27848 KB |
Output is correct |
2 |
Correct |
80 ms |
27940 KB |
Output is correct |
3 |
Correct |
81 ms |
28024 KB |
Output is correct |
4 |
Correct |
81 ms |
27812 KB |
Output is correct |
5 |
Correct |
70 ms |
27916 KB |
Output is correct |
6 |
Correct |
68 ms |
29020 KB |
Output is correct |
7 |
Correct |
79 ms |
30660 KB |
Output is correct |
8 |
Correct |
83 ms |
29888 KB |
Output is correct |
9 |
Correct |
73 ms |
29212 KB |
Output is correct |
10 |
Correct |
65 ms |
27816 KB |
Output is correct |
11 |
Correct |
67 ms |
29060 KB |
Output is correct |
12 |
Correct |
72 ms |
29200 KB |
Output is correct |
13 |
Correct |
68 ms |
29100 KB |
Output is correct |
14 |
Correct |
62 ms |
28868 KB |
Output is correct |
15 |
Correct |
54 ms |
28612 KB |
Output is correct |
16 |
Correct |
41 ms |
27576 KB |
Output is correct |
17 |
Correct |
53 ms |
29480 KB |
Output is correct |
18 |
Correct |
51 ms |
29372 KB |
Output is correct |
19 |
Correct |
52 ms |
29436 KB |
Output is correct |
20 |
Correct |
53 ms |
29480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23756 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Runtime error |
692 ms |
1048580 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
27888 KB |
Output is correct |
2 |
Correct |
67 ms |
27872 KB |
Output is correct |
3 |
Runtime error |
902 ms |
1048580 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
530 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
530 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |