oj.uz

Submission #952425

# Submission time Handle Problem Language Result Execution time Memory
952425 2024-03-23T21:03:10 Z Itamar Duathlon (APIO18_duathlon) C++14
31 / 100
 1000 ms 21584 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];
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) {
    if (vist[i])return 0;
    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;
            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
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1028 ms 7000 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 1028 ms 7000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 19400 KB Output is correct
2 Correct 63 ms 19420 KB Output is correct
3 Correct 93 ms 18256 KB Output is correct
4 Correct 77 ms 18340 KB Output is correct
5 Correct 67 ms 16028 KB Output is correct
6 Correct 77 ms 17540 KB Output is correct
7 Correct 79 ms 15988 KB Output is correct
8 Correct 72 ms 16288 KB Output is correct
9 Correct 71 ms 14740 KB Output is correct
10 Correct 73 ms 14932 KB Output is correct
11 Correct 59 ms 13140 KB Output is correct
12 Correct 59 ms 12884 KB Output is correct
13 Correct 57 ms 12884 KB Output is correct
14 Correct 51 ms 12796 KB Output is correct
15 Correct 43 ms 12768 KB Output is correct
16 Correct 43 ms 12368 KB Output is correct
17 Correct 5 ms 7516 KB Output is correct
18 Correct 4 ms 7516 KB Output is correct
19 Correct 6 ms 7696 KB Output is correct
20 Correct 4 ms 7628 KB Output is correct
21 Correct 4 ms 7516 KB Output is correct
22 Correct 4 ms 7692 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7260 KB Output is correct
6 Correct 2 ms 7000 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7124 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 3 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 3 ms 7004 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7120 KB Output is correct
19 Correct 2 ms 7124 KB Output is correct
20 Correct 2 ms 7000 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 14912 KB Output is correct
2 Correct 71 ms 15076 KB Output is correct
3 Correct 81 ms 15500 KB Output is correct
4 Correct 73 ms 14932 KB Output is correct
5 Correct 71 ms 14868 KB Output is correct
6 Correct 83 ms 21584 KB Output is correct
7 Correct 79 ms 19540 KB Output is correct
8 Correct 81 ms 18360 KB Output is correct
9 Correct 77 ms 17056 KB Output is correct
10 Correct 77 ms 14932 KB Output is correct
11 Correct 76 ms 14820 KB Output is correct
12 Correct 73 ms 15016 KB Output is correct
13 Correct 73 ms 14928 KB Output is correct
14 Correct 73 ms 14672 KB Output is correct
15 Correct 60 ms 14420 KB Output is correct
16 Correct 43 ms 12880 KB Output is correct
17 Correct 75 ms 16928 KB Output is correct
18 Correct 62 ms 16672 KB Output is correct
19 Correct 64 ms 16592 KB Output is correct
20 Correct 62 ms 16328 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14924 KB Output is correct
2 Correct 72 ms 14900 KB Output is correct
3 Incorrect 77 ms 13752 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 1028 ms 7000 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 1028 ms 7000 KB Time limit exceeded
2 Halted 0 ms 0 KB -