oj.uz

Submission #952408

# Submission time Handle Problem Language Result Execution time Memory
952408 2024-03-23T19:15:28 Z Itamar Duathlon (APIO18_duathlon) C++14
0 / 100
 1000 ms 21588 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];
void dfs(int i) {
    if (vis[i])return;
    vis[i] = 1;
    for (int f : fr[i]) {
        if (!vis[f]) {
            pad[f] = i;
            dfs(f);
        }
        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) {
    vist[i] = 1;
    vll v;
    int sum = w[i];
    for (int f : frt[i]) {
        if (!vist[f]) {
            v.push_back(dfst(f));
            sum += v.back();
        }
    }
    v.push_back(n - sum);
    ans += (w[i] * (w[i] - 1)) * (n - 2);
    for (ll k : v) {
        ans += w[i] * k * (n - 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;
            dfs(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]);
            }
        }
    }
    dfst(c[0]);
    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 1041 ms 6492 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 1041 ms 6492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17760 KB Output is correct
2 Correct 66 ms 17592 KB Output is correct
3 Incorrect 62 ms 16192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Incorrect 2 ms 6748 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14932 KB Output is correct
2 Correct 71 ms 14780 KB Output is correct
3 Correct 77 ms 15000 KB Output is correct
4 Correct 71 ms 14928 KB Output is correct
5 Correct 74 ms 14884 KB Output is correct
6 Correct 78 ms 21588 KB Output is correct
7 Correct 92 ms 19536 KB Output is correct
8 Correct 87 ms 18292 KB Output is correct
9 Correct 76 ms 16996 KB Output is correct
10 Incorrect 69 ms 14996 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14932 KB Output is correct
2 Correct 74 ms 14720 KB Output is correct
3 Incorrect 77 ms 13888 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 1041 ms 6492 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 1041 ms 6492 KB Time limit exceeded
2 Halted 0 ms 0 KB -