oj.uz

Submission #952417

# Submission time Handle Problem Language Result Execution time Memory
952417 2024-03-23T19:55:09 Z Itamar Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 21844 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] * (w[i] - 1)) * (t - 2);
    for (ll k : v) {
        ans += w[i] * k * (t - 1 - k);
        ans -= 2 * k * (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 1037 ms 7512 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 1037 ms 7512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 19692 KB Output is correct
2 Correct 65 ms 19740 KB Output is correct
3 Correct 74 ms 18584 KB Output is correct
4 Correct 95 ms 18512 KB Output is correct
5 Correct 72 ms 16220 KB Output is correct
6 Correct 73 ms 17744 KB Output is correct
7 Correct 79 ms 15956 KB Output is correct
8 Correct 70 ms 16464 KB Output is correct
9 Correct 71 ms 14772 KB Output is correct
10 Correct 69 ms 14964 KB Output is correct
11 Correct 66 ms 13396 KB Output is correct
12 Correct 57 ms 13400 KB Output is correct
13 Correct 55 ms 13392 KB Output is correct
14 Correct 53 ms 13140 KB Output is correct
15 Correct 42 ms 12960 KB Output is correct
16 Correct 43 ms 12624 KB Output is correct
17 Correct 5 ms 8028 KB Output is correct
18 Correct 5 ms 8028 KB Output is correct
19 Correct 5 ms 8024 KB Output is correct
20 Correct 5 ms 8028 KB Output is correct
21 Correct 5 ms 8016 KB Output is correct
22 Correct 5 ms 8028 KB Output is correct

Subtask #4
10.0 / 10.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 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 2 ms 7520 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 3 ms 7516 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 3 ms 7704 KB Output is correct
16 Correct 2 ms 7512 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7512 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7552 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15448 KB Output is correct
2 Correct 73 ms 15344 KB Output is correct
3 Correct 88 ms 15524 KB Output is correct
4 Correct 81 ms 15444 KB Output is correct
5 Correct 73 ms 15440 KB Output is correct
6 Correct 84 ms 21844 KB Output is correct
7 Correct 81 ms 19796 KB Output is correct
8 Correct 98 ms 18772 KB Output is correct
9 Correct 78 ms 17664 KB Output is correct
10 Correct 71 ms 15440 KB Output is correct
11 Correct 75 ms 15188 KB Output is correct
12 Correct 84 ms 15272 KB Output is correct
13 Correct 79 ms 15184 KB Output is correct
14 Correct 69 ms 15080 KB Output is correct
15 Correct 62 ms 14672 KB Output is correct
16 Correct 42 ms 13136 KB Output is correct
17 Correct 68 ms 16720 KB Output is correct
18 Correct 64 ms 16712 KB Output is correct
19 Correct 62 ms 16844 KB Output is correct
20 Correct 67 ms 16468 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 6 ms 7512 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 106 ms 15440 KB Output is correct
2 Correct 73 ms 15252 KB Output is correct
3 Incorrect 87 ms 14416 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 1037 ms 7512 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 1037 ms 7512 KB Time limit exceeded
2 Halted 0 ms 0 KB -