oj.uz

Submission #440052

# Submission time Handle Problem Language Result Execution time Memory
440052 2021-07-01T14:17:21 Z VladM Duathlon (APIO18_duathlon) C++14
10 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>

using namespace std;

#define DIM 100007

long long res, cnt[DIM], sz[2*DIM], pnt[2*DIM], n, m, u, v, vis[2*DIM], used[DIM], tin[DIM], tmin[DIM], timer, comps;

set<long long> vec[2*DIM];

set<long long> p;

vector<pair<long long, long long> > edge;

void dfs(long long v, long long par)
{
    used[v]=1;
    tin[v]=tmin[v]=++timer;
    long long ch_cnt=0;
    for(auto to : vec[v])
    {
        if(to==par) continue;
        if(used[to]==0)
        {
            dfs(to, v);
            ch_cnt++;
            tmin[v]=min(tmin[v], tmin[to]);
            if(par!=-1 && tmin[to]>=tin[v])
            {
                p.insert(v);
                pnt[v]=1;
            }
        }
        else tmin[v]=min(tmin[v], tin[to]);
    }
    if(par==-1 && ch_cnt>1)
    {
        p.insert(v);
        pnt[v]=1;
    }
    return;
}

void find_comp(long long v)
{
    vis[v]=comps;
    cnt[comps]++;
    for(auto to : vec[v])
    {
        if(vis[to]!=0) continue;
        find_comp(to);
    }
    return;
}

void buildtree(long long v, long long par)
{
    if(v<=n) sz[v]+=1;
    sz[v]+=cnt[v-n];
    for(auto to : vec[v])
    {
        if(to==par) continue;
        sz[to]+=sz[v];
        buildtree(to, v);
    }
    return;
}

void get_res(long long v)
{
    for(int i=1; i<=2*n; i++) sz[i]=0;
    buildtree(v, -1);
    /*printf("%lld:\n", v);
    for(int i=1; i<=2*n; i++) printf("%lld ", sz[i]);
    printf("\n");*/
    for(auto u : p)
    {
        if(sz[u]<2 || u==v) continue;
        res+=sz[v]*(sz[u]-2);
    }
    for(int i=1; i<=comps; i++)
    {
        if(sz[i+n]<2 || i+n==v) continue;
        res+=sz[v]*(sz[i+n]-2)*cnt[i];
    }
    long long ns=vec[v].size();
    for(int i=0; i<ns; i++)
    {
        res+=sz[v]*(sz[v]-1);
    }
    res+=sz[v]*(sz[v]-1)*(sz[v]-2);
    return;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for(int i=0; i<m; i++)
    {
        scanf("%lld%lld", &u, &v);
        vec[v].insert(u);
        vec[u].insert(v);
    }
    for(int i=1; i<=n; i++)
    {
        if(used[i]==0) dfs(i, -1);
    }
    for(auto v : p)
    {
        for(auto to : vec[v])
        {
            vec[to].erase(v);
            edge.push_back({v, to});
        }
        vec[v].clear();
    }
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0 && pnt[i]==0)
        {
            comps++;
            find_comp(i);
        }
    }
    for(auto P : edge)
    {
        v=P.first;
        u=P.second;
        if(pnt[u])
        {
            vec[v].insert(u);
            vec[u].insert(v);
            continue;
        }
        vec[v].insert(vis[u]+n);
        vec[vis[u]+n].insert(v);
    }
    for(auto u : p) get_res(u);
    for(int i=1; i<=comps; i++) get_res(i+n);
    printf("%lld", res);
    return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%lld%lld", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%lld%lld", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9748 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Runtime error 744 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9748 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Runtime error 744 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 33144 KB Output is correct
2 Correct 204 ms 33148 KB Output is correct
3 Execution timed out 1091 ms 32432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9932 KB Output is correct
2 Correct 39 ms 9944 KB Output is correct
3 Correct 42 ms 9952 KB Output is correct
4 Correct 49 ms 9960 KB Output is correct
5 Correct 49 ms 9984 KB Output is correct
6 Correct 47 ms 9932 KB Output is correct
7 Correct 50 ms 9932 KB Output is correct
8 Correct 45 ms 9932 KB Output is correct
9 Correct 46 ms 9956 KB Output is correct
10 Correct 39 ms 9932 KB Output is correct
11 Correct 34 ms 9932 KB Output is correct
12 Correct 25 ms 9932 KB Output is correct
13 Correct 22 ms 9828 KB Output is correct
14 Correct 15 ms 9932 KB Output is correct
15 Correct 13 ms 9928 KB Output is correct
16 Correct 11 ms 9788 KB Output is correct
17 Correct 28 ms 10016 KB Output is correct
18 Correct 27 ms 9804 KB Output is correct
19 Correct 30 ms 9804 KB Output is correct
20 Correct 28 ms 9904 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 29072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9804 KB Output is correct
2 Correct 41 ms 9956 KB Output is correct
3 Runtime error 851 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 28908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9748 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Runtime error 744 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9748 KB Output is correct
3 Correct 7 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 9 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Runtime error 744 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -