oj.uz

Submission #111220

# Submission time Handle Problem Language Result Execution time Memory
111220 2019-05-14T10:33:07 Z SamAnd Duathlon (APIO18_duathlon) C++17
66 / 100
 544 ms 44924 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;

int n, m;
vector<int> a[N];

long long ans;

int c[N];
int tin[N], ti;
int fup[N];
set<pair<int, int> > s;
void dfs0(int x, int p)
{
    c[x] = 1;
    fup[x] = tin[x] = ti++;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        if (c[h])
        {
            fup[x] = min(fup[x], tin[h]);
        }
        else
        {
            dfs0(h, x);
            if (tin[x] < fup[h])
            {
                s.insert(m_p(x, h));
                s.insert(m_p(h, x));
            }
            fup[x] = min(fup[x], fup[h]);
        }
    }
}

int k;
void dfs01(int x)
{
    c[x] = k;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (s.find(m_p(x, h)) != s.end())
            continue;
        if (!c[h])
            dfs01(h);
    }
}

int cc[N];
int kk;
void dfs02(int x)
{
    cc[x] = kk;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (!cc[h])
            dfs02(h);
    }
}

vector<int> v[N];

vector<int> t[N];
vector<int> g[N];
vector<int> gg[N];

int px[N];
int pp[N];
int q[N];
void dfs03(int x, int p, int u)
{
    pp[x] = u;
    q[x] = v[x].size();
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        px[h] = gg[x][i];
        dfs03(h, x, u);
        q[x] += q[h];
    }
}

void solv0()
{
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
            dfs0(i, i);
    }
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            ++k;
            dfs01(i);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!cc[i])
        {
            ++kk;
            dfs02(i);
        }
    }

    for (set<pair<int, int> >::iterator it = s.begin(); it != s.end(); ++it)
    {
        g[c[(*it).first]].push_back(c[(*it).second]);
        gg[c[(*it).first]].push_back((*it).first);
        t[(*it).first].push_back((*it).second);
    }

    for (int i = 1; i <= n; ++i)
        v[c[i]].push_back(i);

    for (int i = 1; i <= k; ++i)
    {
        if (!pp[i])
            dfs03(i, i, i);
    }

    for (int i = 1; i <= k; ++i)
    {
        long long ysum = 0;
        vector<long long> sum;
        sum.assign(v[i].size(), 0);
        for (int j = 0; j < v[i].size(); ++j)
        {
            int x = v[i][j];
            for (int k = 0; k < t[x].size(); ++k)
            {
                int y = t[x][k];
                if (y != px[i])
                    sum[j] += q[c[y]];
                else
                    sum[j] += (q[pp[i]] - q[i]);
            }
            for (int k = 0; k < t[x].size(); ++k)
            {
                int y = t[x][k];
                if (y != px[i])
                {
                    sum[j] -= q[c[y]];
                    ans += (sum[j] * q[c[y]]);
                    sum[j] += q[c[y]];
                }
                else
                {
                    sum[j] -= (q[pp[i]] - q[i]);
                    ans += (sum[j] * (q[pp[i]] - q[i]));
                    sum[j] += (q[pp[i]] - q[i]);
                }
            }
            sum[j]++;
            ysum += sum[j];
        }
        long long yysum = 0;
        for (int j = 0; j < v[i].size(); ++j)
        {
            ysum -= sum[j];
            ans += ((sum[j] - 1) * ysum) * 2;
            yysum += (sum[j] * ysum);
            ysum += sum[j];
        }
        for (int j = 0; j < v[i].size(); ++j)
        {
            ysum -= sum[j];
            yysum -= (sum[j] * ysum) * 2;
            ans += yysum;
            yysum += (sum[j] * ysum) * 2;
            ysum += sum[j];
        }
    }
    cout << ans << endl;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    solv0();
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void dfs0(int, int)':
count_triplets.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs01(int)':
count_triplets.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs02(int)':
count_triplets.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs03(int, int, int)':
count_triplets.cpp:81:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void solv0()':
count_triplets.cpp:138:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:141:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < t[x].size(); ++k)
                             ~~^~~~~~~~~~~~~
count_triplets.cpp:149:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < t[x].size(); ++k)
                             ~~^~~~~~~~~~~~~
count_triplets.cpp:169:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
count_triplets.cpp:176:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 12 ms 12544 KB Output is correct
5 Correct 14 ms 12672 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 12 ms 12416 KB Output is correct
8 Incorrect 16 ms 12544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 12 ms 12544 KB Output is correct
5 Correct 14 ms 12672 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 12 ms 12416 KB Output is correct
8 Incorrect 16 ms 12544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 27560 KB Output is correct
2 Correct 217 ms 27528 KB Output is correct
3 Correct 347 ms 33780 KB Output is correct
4 Correct 290 ms 30540 KB Output is correct
5 Correct 408 ms 28272 KB Output is correct
6 Correct 387 ms 33304 KB Output is correct
7 Correct 481 ms 32864 KB Output is correct
8 Correct 407 ms 33784 KB Output is correct
9 Correct 387 ms 31864 KB Output is correct
10 Correct 325 ms 30632 KB Output is correct
11 Correct 298 ms 28252 KB Output is correct
12 Correct 288 ms 28152 KB Output is correct
13 Correct 324 ms 28696 KB Output is correct
14 Correct 308 ms 28024 KB Output is correct
15 Correct 253 ms 28536 KB Output is correct
16 Correct 201 ms 27768 KB Output is correct
17 Correct 28 ms 17920 KB Output is correct
18 Correct 27 ms 17920 KB Output is correct
19 Correct 27 ms 17920 KB Output is correct
20 Correct 37 ms 17912 KB Output is correct
21 Correct 30 ms 17792 KB Output is correct
22 Correct 26 ms 17792 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12800 KB Output is correct
2 Correct 12 ms 12800 KB Output is correct
3 Correct 15 ms 12800 KB Output is correct
4 Correct 15 ms 12800 KB Output is correct
5 Correct 15 ms 12800 KB Output is correct
6 Correct 17 ms 12800 KB Output is correct
7 Correct 16 ms 12800 KB Output is correct
8 Correct 15 ms 12800 KB Output is correct
9 Correct 14 ms 12800 KB Output is correct
10 Correct 15 ms 12800 KB Output is correct
11 Correct 20 ms 12800 KB Output is correct
12 Correct 14 ms 12800 KB Output is correct
13 Correct 14 ms 12832 KB Output is correct
14 Correct 14 ms 12672 KB Output is correct
15 Correct 14 ms 12716 KB Output is correct
16 Correct 13 ms 12672 KB Output is correct
17 Correct 14 ms 12840 KB Output is correct
18 Correct 13 ms 12800 KB Output is correct
19 Correct 15 ms 12800 KB Output is correct
20 Correct 16 ms 12800 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 40284 KB Output is correct
2 Correct 449 ms 40312 KB Output is correct
3 Correct 443 ms 40312 KB Output is correct
4 Correct 456 ms 40412 KB Output is correct
5 Correct 447 ms 40312 KB Output is correct
6 Correct 459 ms 44924 KB Output is correct
7 Correct 481 ms 43384 KB Output is correct
8 Correct 469 ms 42488 KB Output is correct
9 Correct 495 ms 41692 KB Output is correct
10 Correct 478 ms 40312 KB Output is correct
11 Correct 500 ms 40312 KB Output is correct
12 Correct 544 ms 40316 KB Output is correct
13 Correct 460 ms 40312 KB Output is correct
14 Correct 433 ms 39032 KB Output is correct
15 Correct 383 ms 37544 KB Output is correct
16 Correct 248 ms 32092 KB Output is correct
17 Correct 380 ms 41580 KB Output is correct
18 Correct 396 ms 41636 KB Output is correct
19 Correct 444 ms 41864 KB Output is correct
20 Correct 483 ms 41732 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12800 KB Output is correct
2 Correct 17 ms 12800 KB Output is correct
3 Correct 13 ms 12672 KB Output is correct
4 Correct 15 ms 12672 KB Output is correct
5 Correct 13 ms 12544 KB Output is correct
6 Correct 14 ms 12544 KB Output is correct
7 Correct 14 ms 12544 KB Output is correct
8 Correct 15 ms 12592 KB Output is correct
9 Correct 13 ms 12544 KB Output is correct
10 Correct 15 ms 12544 KB Output is correct
11 Correct 13 ms 12544 KB Output is correct
12 Correct 16 ms 12800 KB Output is correct
13 Correct 16 ms 12708 KB Output is correct
14 Correct 14 ms 12672 KB Output is correct
15 Correct 15 ms 12688 KB Output is correct
16 Correct 14 ms 12672 KB Output is correct
17 Correct 15 ms 12700 KB Output is correct
18 Correct 14 ms 12544 KB Output is correct
19 Correct 14 ms 12672 KB Output is correct
20 Correct 18 ms 12544 KB Output is correct
21 Correct 13 ms 12672 KB Output is correct
22 Correct 17 ms 12672 KB Output is correct
23 Correct 14 ms 12672 KB Output is correct
24 Correct 14 ms 12672 KB Output is correct
25 Correct 13 ms 12544 KB Output is correct
26 Correct 14 ms 12544 KB Output is correct
27 Correct 14 ms 12488 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 40428 KB Output is correct
2 Correct 493 ms 40056 KB Output is correct
3 Correct 476 ms 32760 KB Output is correct
4 Correct 399 ms 26744 KB Output is correct
5 Correct 298 ms 22344 KB Output is correct
6 Correct 276 ms 20736 KB Output is correct
7 Correct 248 ms 19964 KB Output is correct
8 Correct 247 ms 19192 KB Output is correct
9 Correct 236 ms 18684 KB Output is correct
10 Correct 237 ms 18500 KB Output is correct
11 Correct 229 ms 18040 KB Output is correct
12 Correct 214 ms 17784 KB Output is correct
13 Correct 204 ms 17836 KB Output is correct
14 Correct 207 ms 19932 KB Output is correct
15 Correct 458 ms 36472 KB Output is correct
16 Correct 461 ms 35192 KB Output is correct
17 Correct 493 ms 32528 KB Output is correct
18 Correct 439 ms 31096 KB Output is correct
19 Correct 394 ms 26800 KB Output is correct
20 Correct 369 ms 26628 KB Output is correct
21 Correct 385 ms 26612 KB Output is correct
22 Correct 321 ms 25180 KB Output is correct
23 Correct 248 ms 23452 KB Output is correct
24 Correct 433 ms 33076 KB Output is correct
25 Correct 457 ms 33372 KB Output is correct
26 Correct 498 ms 29100 KB Output is correct
27 Correct 424 ms 29012 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 12 ms 12544 KB Output is correct
5 Correct 14 ms 12672 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 12 ms 12416 KB Output is correct
8 Incorrect 16 ms 12544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 12 ms 12416 KB Output is correct
4 Correct 12 ms 12544 KB Output is correct
5 Correct 14 ms 12672 KB Output is correct
6 Correct 14 ms 12416 KB Output is correct
7 Correct 12 ms 12416 KB Output is correct
8 Incorrect 16 ms 12544 KB Output isn't correct
9 Halted 0 ms 0 KB -