oj.uz

Submission #54116

# Submission time Handle Problem Language Result Execution time Memory
54116 2018-07-02T11:50:48 Z bogdan10bos Duathlon (APIO18_duathlon) C++14
31 / 100
 297 ms 58160 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

int N, M;

namespace Biconnex
{
    int h[400005], low[400005];
    vector<int> edg[400005];
    stack<int> stv;

    int K = 0;
    vector<int> bcx[400005], cmp[400005];

    void addEdge(int x, int y)
    {
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    void DFS(int nod, int fth = 0)
    {
        h[nod] = h[fth] + 1;
        low[nod] = h[nod];
        stv.push(nod);
        for(auto nxt: edg[nod])
        {
            if(nxt == fth)  continue;
            if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }

            stv.push(nod);
            DFS(nxt, nod);
            low[nod] = min(low[nod], low[nxt]);
            if(low[nxt] >= h[nod])
            {
                K++;
                while(stv.top() != nod)
                {
                    int x = stv.top();
                    cmp[K].push_back(x);
                    bcx[x].push_back(K);
                    stv.pop();
                }
                cmp[K].push_back(nod);
                bcx[nod].push_back(K);
                stv.pop();
            }
        }
    }

    void getbiconnex()
    {
        for(int i = 1; i <= N; i++)
            if(!h[i])
                DFS(i);

        for(int i = 1; i <= K; i++)
            cmp[i].erase(unique(cmp[i].begin(), cmp[i].end()), cmp[i].end());
        for(int i = 1; i <= N; i++)
            bcx[i].erase(unique(bcx[i].begin(), bcx[i].end()), bcx[i].end());
    }
}

namespace Tree
{
    int N, K;
    LL ans;
    int f[400005], viz[400005];
    int valuare[400005], val[400005], sz[400005], cmp[400005];
    vector<int> edg[400005];

    void addEdge(int x, int y)
    {
        f[x] = f[y] = 1;
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    void setValue(int x, int y) { f[x] = 1; val[x] = y; }

    void DFS(int nod, int fth = 0)
    {
        if(fth == 0)    cmp[nod] = nod;
        else    cmp[nod] = cmp[fth];
        viz[nod] = 1;
        valuare[nod] = val[nod] == -1 ? 1 : val[nod] - edg[nod].size();
        sz[nod] = valuare[nod];
        for(auto nxt: edg[nod])
        {
            if(nxt == fth)  continue;

            DFS(nxt, nod);
            sz[nod] += sz[nxt];
        }
    }

    void solve()
    {
        ans = 0;

        for(int i = 1; i <= N; i++)
            if(f[i])
                setValue(i, -1);

        for(int i = 1; i <= N + K; i++)
            if(f[i] && !viz[i])
                DFS(i);

        for(int i = N + 1; i <= N + K; i++)
            if(f[i])
                ans += 1LL * val[i] * (val[i] - 1) * (val[i] - 2);

        for(int i = 1; i <= N; i++)
            if(f[i])
            {
                int nod = i;
                int M = sz[ cmp[i] ];
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 1LL * sz[nxt] * (M - sz[nxt] - 1);
                }
                ans += 1LL * (sz[nod] - 1) * (M - sz[nod]);
            }
        for(int i = N + 1; i <= N + K; i++)
            if(f[i])
            {
                int nod = i;
                int M = sz[ cmp[i] ];
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 1LL * (sz[nxt] - 1) * (M - sz[nxt] + 1 - val[nod]) * valuare[i];
                }
                if(sz[nod] != M)    ans += 1LL * valuare[i] * (M - sz[nod] - 1) * (sz[nod] - val[nod] + 1);
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 1LL * (val[i] - 1) * (val[i] - 2) * (sz[nxt] - 1);
                }
                if(sz[nod] != M)    ans += 1LL * (val[i] - 1) * (val[i] - 2) * (M - sz[nod] - 1);
            }

        printf("%lld\n", ans);
    }
}

void makeTree()
{
    using namespace Biconnex;
    for(int i = 1; i <= K; i++)
    {
        if(cmp[i].size() > 2)
        {
            Tree::setValue(i + N, cmp[i].size());
            for(auto &nod: cmp[i])
                if(bcx[nod].size() > 1)
                    Tree::addEdge(i + N, nod);
        }
        else
        {
            Tree::addEdge(cmp[i][0], cmp[i][1]);
        }
    }
    Tree::N = N;
    Tree::K = K;
}

void gen()
{
    freopen("1.in", "w", stdout);
    int N = 1e5;
    printf("%d %d\n", N, N);
    for(int i = 1; i < N; i++)
        printf("%d %d\n", i, i + 1);
    printf("%d %d\n", 1, N);
    exit(0);
}

int main()
{
    //gen();

    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        Biconnex::addEdge(x, y);
    }

    Biconnex::getbiconnex();

    makeTree();

    Tree::solve();

    return 0;
}

Compilation message

count_triplets.cpp: In function 'void gen()':
count_triplets.cpp:176:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:194:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:198:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37880 KB Output is correct
2 Correct 33 ms 37988 KB Output is correct
3 Correct 35 ms 38024 KB Output is correct
4 Correct 36 ms 38104 KB Output is correct
5 Correct 36 ms 38168 KB Output is correct
6 Correct 34 ms 38168 KB Output is correct
7 Incorrect 36 ms 38168 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37880 KB Output is correct
2 Correct 33 ms 37988 KB Output is correct
3 Correct 35 ms 38024 KB Output is correct
4 Correct 36 ms 38104 KB Output is correct
5 Correct 36 ms 38168 KB Output is correct
6 Correct 34 ms 38168 KB Output is correct
7 Incorrect 36 ms 38168 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 53908 KB Output is correct
2 Correct 163 ms 53908 KB Output is correct
3 Correct 201 ms 55012 KB Output is correct
4 Correct 234 ms 55776 KB Output is correct
5 Correct 194 ms 55776 KB Output is correct
6 Correct 221 ms 55776 KB Output is correct
7 Correct 197 ms 55776 KB Output is correct
8 Correct 211 ms 55776 KB Output is correct
9 Correct 233 ms 55776 KB Output is correct
10 Correct 252 ms 55776 KB Output is correct
11 Correct 211 ms 55776 KB Output is correct
12 Correct 214 ms 55776 KB Output is correct
13 Correct 182 ms 55776 KB Output is correct
14 Correct 160 ms 55776 KB Output is correct
15 Correct 150 ms 55776 KB Output is correct
16 Correct 135 ms 55776 KB Output is correct
17 Correct 37 ms 55776 KB Output is correct
18 Correct 38 ms 55776 KB Output is correct
19 Correct 45 ms 55776 KB Output is correct
20 Correct 38 ms 55776 KB Output is correct
21 Correct 49 ms 55776 KB Output is correct
22 Correct 38 ms 55776 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 55776 KB Output is correct
2 Correct 36 ms 55776 KB Output is correct
3 Correct 35 ms 55776 KB Output is correct
4 Correct 38 ms 55776 KB Output is correct
5 Correct 34 ms 55776 KB Output is correct
6 Correct 36 ms 55776 KB Output is correct
7 Correct 35 ms 55776 KB Output is correct
8 Correct 32 ms 55776 KB Output is correct
9 Correct 38 ms 55776 KB Output is correct
10 Correct 43 ms 55776 KB Output is correct
11 Correct 32 ms 55776 KB Output is correct
12 Correct 34 ms 55776 KB Output is correct
13 Correct 35 ms 55776 KB Output is correct
14 Correct 33 ms 55776 KB Output is correct
15 Correct 35 ms 55776 KB Output is correct
16 Correct 40 ms 55776 KB Output is correct
17 Correct 33 ms 55776 KB Output is correct
18 Correct 33 ms 55776 KB Output is correct
19 Correct 37 ms 55776 KB Output is correct
20 Correct 33 ms 55776 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 55776 KB Output is correct
2 Correct 213 ms 55776 KB Output is correct
3 Correct 212 ms 55776 KB Output is correct
4 Correct 193 ms 55776 KB Output is correct
5 Correct 198 ms 55776 KB Output is correct
6 Correct 191 ms 58160 KB Output is correct
7 Correct 194 ms 58160 KB Output is correct
8 Correct 208 ms 58160 KB Output is correct
9 Correct 212 ms 58160 KB Output is correct
10 Correct 236 ms 58160 KB Output is correct
11 Correct 287 ms 58160 KB Output is correct
12 Correct 223 ms 58160 KB Output is correct
13 Correct 222 ms 58160 KB Output is correct
14 Correct 194 ms 58160 KB Output is correct
15 Correct 167 ms 58160 KB Output is correct
16 Correct 156 ms 58160 KB Output is correct
17 Correct 159 ms 58160 KB Output is correct
18 Correct 207 ms 58160 KB Output is correct
19 Correct 163 ms 58160 KB Output is correct
20 Correct 187 ms 58160 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37880 KB Output is correct
2 Correct 33 ms 37988 KB Output is correct
3 Correct 35 ms 38024 KB Output is correct
4 Correct 36 ms 38104 KB Output is correct
5 Correct 36 ms 38168 KB Output is correct
6 Correct 34 ms 38168 KB Output is correct
7 Incorrect 36 ms 38168 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37880 KB Output is correct
2 Correct 33 ms 37988 KB Output is correct
3 Correct 35 ms 38024 KB Output is correct
4 Correct 36 ms 38104 KB Output is correct
5 Correct 36 ms 38168 KB Output is correct
6 Correct 34 ms 38168 KB Output is correct
7 Incorrect 36 ms 38168 KB Output isn't correct
8 Halted 0 ms 0 KB -