oj.uz

Submission #618701

# Submission time Handle Problem Language Result Execution time Memory
618701 2022-08-02T06:47:18 Z keta_tsimakuridze Duathlon (APIO18_duathlon) C++14
0 / 100
 298 ms 75832 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
#define int long long
using namespace std;
const int N = 2e5 + 5;
int f[N], low[N], t[N], sz[2 * N], p[N], h[N];
ll bad = 0, s[2 * N];
int n;
vector<int> adj[2 * N];
vector<pii> V[N];
map<int,int> e[N];
int find(int u) {
    return (p[u] == u ? u : p[u] = find(p[u]));
}
void merge(int u, int v) {
    u = find(u), v = find(v);
    p[u] = v;
}
void dfs0(int u, int ID) {
    f[u] = 1;
    low[u] = h[u]; sz[u] = 1;
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f, id = V[u][i].s;
        if(ID == id) continue;
        if(f[v]) low[u] = min(low[u], h[v]);
        else    {
            t[id] = 1;
            h[v] = h[u] + 1;
            dfs0(v, id);
            sz[u] += sz[v];
            if(low[v] < h[u]) merge(ID, id);
            low[u] = min(low[u], low[v]);
        }
    }
}
void dfs(int u, int p) {
    f[u] = -1;
    h[u] = h[p] + 1;
    sz[u] = 0;
    int x = 0;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        x += sz[v] * (sz[v] - 1) / 2;
    }
    if(h[u] % 2) sz[u]++;
    // roca zevit aris
    bad += (n - sz[u] - (1 - h[u] % 2)) * (sz[u] * (sz[u] - 1) / 2 - x);
    if(h[u] % 2 < 2) {
        x += (n - sz[u]) * (n - sz[u] - 1) / 2;
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if(v == p) continue;
            bad += (sz[v] - (1 - h[u] % 2)) * ((n - sz[v]) * (n - sz[v] - 1) / 2 - (x - sz[v] * (sz[v] - 1) / 2));

        }
    }
}
void ADD(int x, int y) {
    x += n;
    if(e[x][y]) return;
    e[x][y] = 1;
    adj[x].push_back(y);
    adj[y].push_back(x);
}
main() {
    int m;
    cin >> n >> m;
    vector<pair<int,int >> e;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back({v, i});
        V[v].push_back({u, i});
        e.push_back({u, v});
        p[i] = i;
    }
    int all = 0;
    for(int i = n; i >= 1; i--) if(!f[i]) dfs0(i, 0), all += sz[i] * (sz[i] - 1) * (sz[i] - 2);
    for(int i = 1; i <= m; i++) {
        if(!t[i]) continue;
        ADD(find(i), e[i - 1].f);
        ADD(find(i), e[i - 1].s);
    }
    for(int i = 1; i <= n; i++)
    if(f[i] != -1) dfs(i, 0);
    cout << all - 2 * bad;

}

Compilation message

count_triplets.cpp: In function 'void dfs0(long long int, long long int)':
count_triplets.cpp:25:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(long long int, long long int)':
count_triplets.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < adj[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
count_triplets.cpp:56:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i = 0; i < adj[u].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
count_triplets.cpp: At global scope:
count_triplets.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main() {
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 54564 KB Output is correct
2 Correct 285 ms 55780 KB Output is correct
3 Incorrect 247 ms 59556 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 14 ms 24044 KB Output is correct
3 Correct 14 ms 24168 KB Output is correct
4 Correct 14 ms 24276 KB Output is correct
5 Correct 14 ms 24248 KB Output is correct
6 Correct 13 ms 24216 KB Output is correct
7 Correct 14 ms 24148 KB Output is correct
8 Correct 14 ms 24092 KB Output is correct
9 Correct 14 ms 24088 KB Output is correct
10 Incorrect 14 ms 24160 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 56836 KB Output is correct
2 Correct 211 ms 58232 KB Output is correct
3 Correct 244 ms 58108 KB Output is correct
4 Correct 214 ms 58248 KB Output is correct
5 Correct 216 ms 58264 KB Output is correct
6 Correct 298 ms 66668 KB Output is correct
7 Correct 240 ms 64248 KB Output is correct
8 Correct 254 ms 62688 KB Output is correct
9 Correct 234 ms 61064 KB Output is correct
10 Incorrect 209 ms 58212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24056 KB Output is correct
2 Correct 15 ms 24148 KB Output is correct
3 Correct 15 ms 24088 KB Output is correct
4 Correct 16 ms 24120 KB Output is correct
5 Correct 15 ms 24060 KB Output is correct
6 Correct 15 ms 24120 KB Output is correct
7 Correct 17 ms 24020 KB Output is correct
8 Correct 14 ms 24112 KB Output is correct
9 Correct 15 ms 24060 KB Output is correct
10 Correct 14 ms 24020 KB Output is correct
11 Correct 16 ms 24148 KB Output is correct
12 Correct 16 ms 24148 KB Output is correct
13 Correct 14 ms 24128 KB Output is correct
14 Correct 15 ms 24176 KB Output is correct
15 Correct 14 ms 24148 KB Output is correct
16 Incorrect 13 ms 24056 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 56972 KB Output is correct
2 Correct 218 ms 58080 KB Output is correct
3 Runtime error 192 ms 75832 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -