oj.uz

Submission #49631

# Submission time Handle Problem Language Result Execution time Memory
49631 2018-06-01T11:38:48 Z SpaimaCarpatilor Duathlon (APIO18_duathlon) C++17
0 / 100
 297 ms 29600 KB 
#include<bits/stdc++.h>

using namespace std;

int nodes, N, M, lev[100009], dp[100009], vol[200009], papa[200009];
long long sumProd[200009];
stack < pair < int, int > > stk;
vector < int > v[100009], h[200009];

void addComp (pair < int, int > whenToStop)
{
    pair < int, int > curr;
    vector < int > currComp;
    do {
        curr = stk.top ();
        stk.pop ();
        currComp.push_back (curr.first);
        currComp.push_back (curr.second);
    }while (curr != whenToStop);
    sort (currComp.begin (), currComp.end ());
    currComp.erase (unique (currComp.begin (), currComp.end ()), currComp.end ());
/*    for (auto it : currComp)
        printf ("%d ", it);
    printf ("\n");*/
    nodes ++;
    for (auto it : currComp)
        h[it].push_back (nodes),
        h[nodes].push_back (it);
}

void dfs (int nod, int tata)
{
    dp[nod] = lev[nod];
    for (auto it : v[nod])
        if (lev[it] == 0)
        {
            lev[it] = lev[nod] + 1;
            stk.push ({it, nod});
            dfs (it, nod);
            if (dp[it] < dp[nod])
                dp[nod] = dp[it];
            if (dp[it] >= lev[nod])
                addComp ({it, nod});
        }
    for (auto it : v[nod])
        if (it != tata)
        {
            if (lev[it] < dp[nod])
                dp[nod] = lev[it];
        }
}

void init (int nod, int tata)
{
    vol[nod] = (nod <= N), papa[nod] = tata;
    int sum = 0;
    for (auto it : h[nod])
        if (it != tata)
            init (it, nod), vol[nod] += vol[it],
            sumProd[nod] += 1LL * sum * vol[it],
            sum += vol[it];
    sumProd[nod] += 1LL * sum * (N - vol[nod]);
    sumProd[nod] <<= 1LL;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
while (M --)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    v[x].push_back (y);
    v[y].push_back (x);
}
lev[1] = 1, nodes = N;
dfs (1, -1), init (1, -1);
long long ans = 0;
for (int x=1; x<=N; x++)
{
    ans += sumProd[x];
    for (auto comp : h[x])
    {
        ans += sumProd[comp];
        if (papa[comp] == x)
            ans -= 2LL * (N - vol[comp]) * vol[comp];
        else
            ans -= 2LL * (N - vol[x]) * vol[x];
    }
}
printf ("%lld\n", ans);
return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:71:7: 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:75:11: 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 Incorrect 7 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 27512 KB Output is correct
2 Correct 104 ms 27536 KB Output is correct
3 Incorrect 85 ms 27536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 27536 KB Output is correct
2 Correct 203 ms 27536 KB Output is correct
3 Correct 210 ms 27536 KB Output is correct
4 Correct 206 ms 27536 KB Output is correct
5 Correct 202 ms 27536 KB Output is correct
6 Correct 216 ms 29600 KB Output is correct
7 Correct 228 ms 29600 KB Output is correct
8 Correct 245 ms 29600 KB Output is correct
9 Correct 213 ms 29600 KB Output is correct
10 Incorrect 134 ms 29600 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 29600 KB Output is correct
2 Correct 210 ms 29600 KB Output is correct
3 Correct 222 ms 29600 KB Output is correct
4 Correct 197 ms 29600 KB Output is correct
5 Correct 198 ms 29600 KB Output is correct
6 Correct 180 ms 29600 KB Output is correct
7 Correct 249 ms 29600 KB Output is correct
8 Correct 167 ms 29600 KB Output is correct
9 Correct 155 ms 29600 KB Output is correct
10 Correct 187 ms 29600 KB Output is correct
11 Correct 168 ms 29600 KB Output is correct
12 Correct 162 ms 29600 KB Output is correct
13 Correct 153 ms 29600 KB Output is correct
14 Correct 166 ms 29600 KB Output is correct
15 Correct 225 ms 29600 KB Output is correct
16 Correct 297 ms 29600 KB Output is correct
17 Correct 211 ms 29600 KB Output is correct
18 Correct 226 ms 29600 KB Output is correct
19 Incorrect 194 ms 29600 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -