oj.uz

Submission #54192

# Submission time Handle Problem Language Result Execution time Memory
54192 2018-07-02T17:41:07 Z bogdan10bos Duathlon (APIO18_duathlon) C++14
31 / 100
 331 ms 58108 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])
            {
                int nod = i;
                int M = sz[ cmp[i] ];

                /// 3 elemente
                ans += 1LL * val[i] * (val[i] - 1) * (val[i] - 2);

                /// 2 elemente
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 2LL * (val[i] - 1) * (val[i] - 1) * (sz[nxt] - 1);
                }
                if(sz[nod] != M)
                {
                    ans += 2LL * (val[i] - 1) * (val[i] - 1) * (M - sz[nod] - 1);
                }

                /// 1 element (mijloc)
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[nod])   continue;
                    ans += 1LL * val[i] * (sz[nxt] - 1) * (M - val[i] - sz[nxt] + 1);
                }
                if(sz[nod] != M)
                {
                    ans += 1LL * val[i] * (M - sz[nod] - 1) * (sz[nod] - val[nod] + 1);
                }
            }

        for(int i = 1; i <= N; i++)
            if(f[i])
            {
                bool ok = true;
                for(auto nxt: edg[i])
                    if(nxt > N) ok = false;
                if(!ok)
                {
                    int cnt = 0;
                    for(auto nxt: edg[i])
                        if(val[nxt] > 0)
                            cnt += val[nxt] - 1;
                    for(auto nxt: edg[i])
                        if(val[nxt] > 0)
                            ans -= 1LL * (val[nxt] - 1) * (cnt - val[nxt] + 1);
                    continue;
                }

                int M = sz[ cmp[i] ];
                for(auto nxt: edg[i])
                {
                    if(sz[nxt] > sz[i]) continue;
                    ans += 1LL * sz[nxt] * (M - sz[nxt] - 1);
                }
                if(sz[i] != M)
                    ans += 1LL * (sz[i] - 1) * (M - sz[i]);
            }

        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:201: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:219: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:223: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 37 ms 38008 KB Output is correct
2 Correct 36 ms 38008 KB Output is correct
3 Correct 33 ms 38048 KB Output is correct
4 Correct 33 ms 38100 KB Output is correct
5 Correct 38 ms 38100 KB Output is correct
6 Correct 37 ms 38128 KB Output is correct
7 Incorrect 39 ms 38176 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38008 KB Output is correct
2 Correct 36 ms 38008 KB Output is correct
3 Correct 33 ms 38048 KB Output is correct
4 Correct 33 ms 38100 KB Output is correct
5 Correct 38 ms 38100 KB Output is correct
6 Correct 37 ms 38128 KB Output is correct
7 Incorrect 39 ms 38176 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 166 ms 53776 KB Output is correct
2 Correct 204 ms 53796 KB Output is correct
3 Correct 213 ms 55008 KB Output is correct
4 Correct 200 ms 55608 KB Output is correct
5 Correct 189 ms 55608 KB Output is correct
6 Correct 205 ms 55608 KB Output is correct
7 Correct 205 ms 55608 KB Output is correct
8 Correct 201 ms 55608 KB Output is correct
9 Correct 212 ms 55608 KB Output is correct
10 Correct 232 ms 55608 KB Output is correct
11 Correct 181 ms 55608 KB Output is correct
12 Correct 165 ms 55608 KB Output is correct
13 Correct 163 ms 55608 KB Output is correct
14 Correct 174 ms 55608 KB Output is correct
15 Correct 142 ms 55608 KB Output is correct
16 Correct 143 ms 55608 KB Output is correct
17 Correct 38 ms 55608 KB Output is correct
18 Correct 40 ms 55608 KB Output is correct
19 Correct 43 ms 55608 KB Output is correct
20 Correct 42 ms 55608 KB Output is correct
21 Correct 43 ms 55608 KB Output is correct
22 Correct 38 ms 55608 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 55608 KB Output is correct
2 Correct 244 ms 55608 KB Output is correct
3 Correct 275 ms 55608 KB Output is correct
4 Correct 265 ms 55608 KB Output is correct
5 Correct 244 ms 55608 KB Output is correct
6 Correct 331 ms 58108 KB Output is correct
7 Correct 223 ms 58108 KB Output is correct
8 Correct 211 ms 58108 KB Output is correct
9 Correct 226 ms 58108 KB Output is correct
10 Correct 211 ms 58108 KB Output is correct
11 Correct 224 ms 58108 KB Output is correct
12 Correct 261 ms 58108 KB Output is correct
13 Correct 315 ms 58108 KB Output is correct
14 Correct 197 ms 58108 KB Output is correct
15 Correct 183 ms 58108 KB Output is correct
16 Correct 149 ms 58108 KB Output is correct
17 Correct 164 ms 58108 KB Output is correct
18 Correct 195 ms 58108 KB Output is correct
19 Correct 210 ms 58108 KB Output is correct
20 Correct 179 ms 58108 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 58108 KB Output is correct
2 Correct 233 ms 58108 KB Output is correct
3 Incorrect 234 ms 58108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38008 KB Output is correct
2 Correct 36 ms 38008 KB Output is correct
3 Correct 33 ms 38048 KB Output is correct
4 Correct 33 ms 38100 KB Output is correct
5 Correct 38 ms 38100 KB Output is correct
6 Correct 37 ms 38128 KB Output is correct
7 Incorrect 39 ms 38176 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 38008 KB Output is correct
2 Correct 36 ms 38008 KB Output is correct
3 Correct 33 ms 38048 KB Output is correct
4 Correct 33 ms 38100 KB Output is correct
5 Correct 38 ms 38100 KB Output is correct
6 Correct 37 ms 38128 KB Output is correct
7 Incorrect 39 ms 38176 KB Output isn't correct
8 Halted 0 ms 0 KB -