oj.uz

Submission #148098

# Submission time Handle Problem Language Result Execution time Memory
148098 2019-08-31T13:52:31 Z WhipppedCream Duathlon (APIO18_duathlon) C++17
31 / 100
 259 ms 43044 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 1e5+5;
const int maxm = 2e5+5;
vii adj[maxn];
int a[maxm];
int b[maxm];
int num[maxn];
bool art[maxn];
int sz[maxm+maxn];
int low[maxn];
int col[maxm];
bool instack[maxn];
int comps = 0;
int treecmp[maxm];
int cnt[maxm+maxn];
vi tree[maxm+maxn];
stack<int> S;
int tim = 1;
void dfs(int u, int p)
{
    num[u] = low[u] = tim++;
    int chil = 0;
    for(auto edge : adj[u])
    {
        int v = edge.X, id = edge.Y;
        if(!num[v])
        {
            if(!instack[id])
            {
                instack[id] = true;
                S.push(id);
            }
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            chil++;
            if((p && num[u]<= low[v]) || (!p && chil> 1))
            {
                art[u] = true;
                comps++;
                while(true)
                {
                    int x = S.top(); S.pop();
                    col[x] = comps;
                    if(x == id) break;
                }
            }
        }
        else if(v != p)
        {
            if(!instack[id])
            {
                S.push(id);
                instack[id] = true;
            }
            low[u] = min(low[u], num[v]);
        }
    }
}
ll tot = 0;
int artcnt = 0;
bool pong[maxn+maxm];
void tfs(int u, int p)
{
    pong[u] = true;
    cnt[u] = sz[u];
    for(auto kk : tree[u])
    {
        int v = kk;
        if(v == p) continue;
        tfs(v, u);
        cnt[u] += cnt[v];
    }
}
void find_ans(int u, int p, int prv)
{
    //printf("call %d: %d, %d\n", u, sz[u], prv);
    if(u> comps)
    {
        int now = prv;
        tot += 2LL*sz[p]*(prv-sz[p]);
        tot += 1LL*sz[p]*(sz[p]-1);
        for(auto v : tree[u])
        {
            if(v == p) continue;
            tot += 2LL*now*cnt[v];
            //printf("here %lld\n", tot);
            tot += 2LL*sz[v]*(cnt[v]-sz[v]);
            tot += 1LL*sz[v]*(sz[v]-1);
            now += cnt[v];
        }
    }
    else
    {
        int now = prv;
        for(auto v : tree[u])
        {
            if(v == p) continue;
            tot += 2LL*sz[u]*cnt[v]*now;
            now += cnt[v];
        }
        //printf("tot before is %lld\n", tot);
        tot += 2LL*(sz[u]-1)*sz[u]*now;
        tot += 1LL*(sz[u])*(sz[u]-1)*(sz[u]-2);
    }
    //printf("tot is now %lld\n", tot);
    for(auto v : tree[u]) if(v != p) find_ans(v, u, prv+cnt[u]-cnt[v]);
}
int main()
{
    int n, m; scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; i++)
    {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].pb(ii(v, i));
        adj[v].pb(ii(u, i));
        a[i] = u; b[i] = v;
    }
    for(int i = 1; i<= n; i++)
    {
        if(num[i]) continue;
        dfs(i, 0);
        comps++;
        while(!S.empty())
        {
            int x = S.top(); S.pop();
            col[x] = comps;
        }
    }
    for(int i = 1; i<= n; i++)
    {
        if(art[i])
        {
            artcnt++;
            treecmp[i] = artcnt+comps;
        }
    }
    for(int i = 1; i<= m; i++)
    {
        int u = a[i], v = b[i];
        if(!art[u]) swap(u, v);
        if(!art[u])
        {
            treecmp[u] = treecmp[v] = col[i];
        }
        else
        {
            tree[treecmp[u]].pb(col[i]);
            tree[col[i]].pb(treecmp[u]);
            //printf("connect %d %d\n", treecmp[u], col[i]);
            if(art[v])
            {
                tree[treecmp[v]].pb(col[i]);
                tree[col[i]].pb(treecmp[v]);
                //printf("connect %d %d\n", treecmp[v], col[i]);
            }
            else
            {
                treecmp[v] = col[i];
            }
        }
    }
    for(int i = 1; i<= comps+artcnt; i++)
    {
        sort(tree[i].begin(), tree[i].end());
        tree[i].resize(unique(tree[i].begin(), tree[i].end())-tree[i].begin());
    }
    //printf("%d, %d\n", comps, artcnt);
    for(int i = 1; i<= n; i++) sz[treecmp[i]]++;
    for(int i = 1; i<= comps+artcnt; i++)
    {
        if(pong[i]) continue;
        tfs(i, 0);
        find_ans(i, 0, 0);
    }
    printf("%lld\n",tot);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:117:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf("%d %d", &n, &m);
               ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:120:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 11 ms 9720 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Incorrect 10 ms 9724 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 110 ms 26340 KB Output is correct
2 Correct 107 ms 26348 KB Output is correct
3 Correct 147 ms 29924 KB Output is correct
4 Correct 130 ms 25592 KB Output is correct
5 Correct 132 ms 25436 KB Output is correct
6 Correct 172 ms 31324 KB Output is correct
7 Correct 142 ms 25064 KB Output is correct
8 Correct 162 ms 28064 KB Output is correct
9 Correct 138 ms 23160 KB Output is correct
10 Correct 130 ms 23736 KB Output is correct
11 Correct 99 ms 18860 KB Output is correct
12 Correct 98 ms 18832 KB Output is correct
13 Correct 79 ms 18040 KB Output is correct
14 Correct 112 ms 18040 KB Output is correct
15 Correct 59 ms 16376 KB Output is correct
16 Correct 60 ms 16376 KB Output is correct
17 Correct 16 ms 11768 KB Output is correct
18 Correct 15 ms 11768 KB Output is correct
19 Correct 15 ms 11640 KB Output is correct
20 Correct 18 ms 11640 KB Output is correct
21 Correct 15 ms 11640 KB Output is correct
22 Correct 14 ms 11640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct
2 Correct 11 ms 9976 KB Output is correct
3 Correct 11 ms 9848 KB Output is correct
4 Correct 11 ms 10104 KB Output is correct
5 Correct 11 ms 9976 KB Output is correct
6 Correct 11 ms 9976 KB Output is correct
7 Correct 12 ms 10104 KB Output is correct
8 Correct 12 ms 9936 KB Output is correct
9 Correct 11 ms 9976 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 11 ms 9848 KB Output is correct
12 Correct 14 ms 9848 KB Output is correct
13 Correct 11 ms 9848 KB Output is correct
14 Correct 11 ms 9820 KB Output is correct
15 Correct 11 ms 9848 KB Output is correct
16 Correct 10 ms 9848 KB Output is correct
17 Correct 11 ms 9848 KB Output is correct
18 Correct 11 ms 9848 KB Output is correct
19 Correct 16 ms 9980 KB Output is correct
20 Correct 11 ms 9848 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 23544 KB Output is correct
2 Correct 145 ms 23416 KB Output is correct
3 Correct 172 ms 23416 KB Output is correct
4 Correct 211 ms 23500 KB Output is correct
5 Correct 148 ms 23448 KB Output is correct
6 Correct 259 ms 43044 KB Output is correct
7 Correct 204 ms 30840 KB Output is correct
8 Correct 183 ms 29048 KB Output is correct
9 Correct 197 ms 27228 KB Output is correct
10 Correct 155 ms 23544 KB Output is correct
11 Correct 156 ms 23564 KB Output is correct
12 Correct 144 ms 23472 KB Output is correct
13 Correct 151 ms 23348 KB Output is correct
14 Correct 130 ms 22396 KB Output is correct
15 Correct 117 ms 21112 KB Output is correct
16 Correct 67 ms 17296 KB Output is correct
17 Correct 79 ms 21736 KB Output is correct
18 Correct 82 ms 21992 KB Output is correct
19 Correct 84 ms 22112 KB Output is correct
20 Correct 86 ms 21736 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9848 KB Output is correct
2 Correct 12 ms 9848 KB Output is correct
3 Incorrect 11 ms 9980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 23432 KB Output is correct
2 Correct 214 ms 23724 KB Output is correct
3 Runtime error 112 ms 33928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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