Submission #618810

#	Time	Username	Problem	Language	Result	Execution time	Memory
618810		keta_tsimakuridze	Duathlon (APIO18_duathlon)	C++14	0 / 100	334 ms	74660 KiB

count_triplets

#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 (stderr)

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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10