oj.uz

Submission #952419

# Submission time Handle Problem Language Result Execution time Memory
952419 2024-03-23T20:13:11 Z Itamar Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 20820 KB 
#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define pd pair<double,double>
#include <stack>

const int siz = 1e5 + 1;
int c[siz];
vi fr[siz];
bool vis[siz];
int pad[siz];
vi frt[siz];
int padt[siz];
ll w[siz];
int sor[siz];
int cum[siz];
void dfs(int i, int so) {
    if (vis[i])return;
    sor[i] = so;
    cum[so]++;
    vis[i] = 1;
    for (int f : fr[i]) {
        if (!vis[f]) {
            pad[f] = i;
            dfs(f,so);
        }
        else if (f != pad[i] && c[i]==i) {
            int k = pad[i];
            while (k != f) {
                w[i]++;
                c[k] = i;
                k = pad[k];
            }
            w[i]++;
            c[k] = i;
        }
    }
}
ll ans = 0;
int n, m;
bool vist[siz];
int dfst(int i, int t) {
    vist[i] = 1;
    vll v;
    int sum = w[i];
    for (int f : frt[i]) {
        if (!vist[f]) {
            v.push_back(dfst(f,t));
            sum += v.back();
        }
    }
    v.push_back(t - sum);
    ans += (w[i] * (t - 1)) * (t - 2);
    for (ll k : v) {
        ans -= w[i] * k * (k - 1);
        ans -= k * 2 * (w[i] - 1);
    }
    return sum;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        fr[a].push_back(b);
        fr[b].push_back(a);
    }
    for (int i = 0; i < n; i++) {
        w[i] = 1;
        c[i] = i;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            pad[i] = i;
            int s = 0;
            dfs(i,i);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int f : fr[i]) {
            if (c[i] != c[f]) {
                frt[c[i]].push_back(c[f]);
            }
        }
    }
    for(int i = 0; i < n; i++)if(!vist[c[i]])dfst(c[i],cum[sor[i]]);
    cout << ans;
}
/*
4 3
1 2
2 3
3 4
*/

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:90:17: warning: unused variable 's' [-Wunused-variable]
   90 |             int s = 0;
      |                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 7260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 7260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 18640 KB Output is correct
2 Correct 67 ms 18772 KB Output is correct
3 Correct 79 ms 17748 KB Output is correct
4 Correct 65 ms 17624 KB Output is correct
5 Correct 70 ms 15420 KB Output is correct
6 Correct 71 ms 16884 KB Output is correct
7 Correct 84 ms 15344 KB Output is correct
8 Correct 70 ms 15700 KB Output is correct
9 Correct 69 ms 14168 KB Output is correct
10 Correct 93 ms 14232 KB Output is correct
11 Correct 60 ms 12636 KB Output is correct
12 Correct 56 ms 12624 KB Output is correct
13 Correct 56 ms 12628 KB Output is correct
14 Correct 56 ms 12400 KB Output is correct
15 Correct 42 ms 12372 KB Output is correct
16 Correct 45 ms 12112 KB Output is correct
17 Correct 6 ms 8028 KB Output is correct
18 Correct 6 ms 8092 KB Output is correct
19 Correct 4 ms 8028 KB Output is correct
20 Correct 4 ms 8028 KB Output is correct
21 Correct 6 ms 8028 KB Output is correct
22 Correct 6 ms 8024 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 2 ms 7604 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7624 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 3 ms 7768 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7512 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7504 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14420 KB Output is correct
2 Correct 97 ms 14416 KB Output is correct
3 Correct 72 ms 14280 KB Output is correct
4 Correct 72 ms 14420 KB Output is correct
5 Correct 74 ms 14420 KB Output is correct
6 Correct 98 ms 20820 KB Output is correct
7 Correct 88 ms 18768 KB Output is correct
8 Correct 77 ms 17776 KB Output is correct
9 Correct 79 ms 16552 KB Output is correct
10 Correct 72 ms 14232 KB Output is correct
11 Correct 71 ms 14416 KB Output is correct
12 Correct 72 ms 14416 KB Output is correct
13 Correct 71 ms 14432 KB Output is correct
14 Correct 66 ms 14344 KB Output is correct
15 Correct 58 ms 13904 KB Output is correct
16 Correct 43 ms 12628 KB Output is correct
17 Correct 64 ms 16072 KB Output is correct
18 Correct 65 ms 16052 KB Output is correct
19 Correct 62 ms 16104 KB Output is correct
20 Correct 62 ms 15792 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Incorrect 2 ms 7516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 14440 KB Output is correct
2 Correct 73 ms 14164 KB Output is correct
3 Incorrect 77 ms 13140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 7260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 7260 KB Time limit exceeded
2 Halted 0 ms 0 KB -