oj.uz

Submission #618810

# Submission time Handle Problem Language Result Execution time Memory
618810 2022-08-02T07:36:27 Z keta_tsimakuridze Duathlon (APIO18_duathlon) C++14
0 / 100
 334 ms 74660 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) {
    h[u] = h[p] + 1;
    sz[u] = 0;
    s[u] = 0;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs(v, u);
        s[u] += s[v] + sz[u] * sz[v];
        sz[u] += sz[v];
    }
    if(h[u] % 2)s[u] += sz[u], sz[u]++;
    if(h[u] == 3) bad += sz[u] * (sz[u] - 1) / 2;
} */
void dfs(int u, int p) {
    sz[u] = 0;
    f[u] = -1;
    h[u] = h[p] + 1;
    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];
    }
    if(h[u] % 2) {
        ++sz[u];
        if(p)
        bad += sz[u] * (sz[u] - 1) / 2 * (adj[p].size() - 1);
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if(v == p) continue;
            bad += ((n - sz[v]) * (n - sz[v] - 1) / 2) * (adj[v].size() - 1);
        }
    }
}
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 <= n; i++) V[i].clear();
    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:57: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]
   57 |     for(int i = 0; i < adj[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
count_triplets.cpp:67: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]
   67 |         for(int i = 0; i < adj[u].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
count_triplets.cpp: At global scope:
count_triplets.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main() {
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 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 12 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 334 ms 54640 KB Output is correct
2 Correct 304 ms 54796 KB Output is correct
3 Incorrect 285 ms 58532 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 24180 KB Output is correct
2 Correct 16 ms 24076 KB Output is correct
3 Correct 15 ms 24136 KB Output is correct
4 Correct 17 ms 24180 KB Output is correct
5 Correct 14 ms 24148 KB Output is correct
6 Correct 19 ms 24148 KB Output is correct
7 Correct 16 ms 24276 KB Output is correct
8 Correct 19 ms 24208 KB Output is correct
9 Correct 16 ms 24128 KB Output is correct
10 Incorrect 18 ms 24180 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 57080 KB Output is correct
2 Correct 276 ms 57184 KB Output is correct
3 Correct 275 ms 57204 KB Output is correct
4 Correct 254 ms 57216 KB Output is correct
5 Correct 301 ms 57228 KB Output is correct
6 Correct 271 ms 65732 KB Output is correct
7 Correct 281 ms 63252 KB Output is correct
8 Correct 319 ms 61576 KB Output is correct
9 Correct 255 ms 59980 KB Output is correct
10 Incorrect 237 ms 57104 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24048 KB Output is correct
2 Correct 18 ms 24148 KB Output is correct
3 Correct 18 ms 24044 KB Output is correct
4 Correct 19 ms 24148 KB Output is correct
5 Correct 18 ms 24096 KB Output is correct
6 Correct 15 ms 24024 KB Output is correct
7 Correct 16 ms 24116 KB Output is correct
8 Correct 15 ms 24020 KB Output is correct
9 Correct 16 ms 24020 KB Output is correct
10 Correct 14 ms 24056 KB Output is correct
11 Correct 17 ms 24084 KB Output is correct
12 Correct 16 ms 24148 KB Output is correct
13 Correct 15 ms 24140 KB Output is correct
14 Correct 17 ms 24188 KB Output is correct
15 Correct 14 ms 24148 KB Output is correct
16 Incorrect 15 ms 24072 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 57020 KB Output is correct
2 Correct 253 ms 56920 KB Output is correct
3 Runtime error 155 ms 74660 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 12 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 12 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -