oj.uz

Submission #57582

# Submission time Handle Problem Language Result Execution time Memory
57582 2018-07-15T09:44:24 Z Crown Duathlon (APIO18_duathlon) C++14
31 / 100
 393 ms 78844 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 12 ms 9848 KB Output is correct
2 Correct 14 ms 9952 KB Output is correct
3 Correct 11 ms 9952 KB Output is correct
4 Correct 13 ms 10072 KB Output is correct
5 Correct 11 ms 10180 KB Output is correct
6 Correct 11 ms 10232 KB Output is correct
7 Incorrect 11 ms 10232 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9848 KB Output is correct
2 Correct 14 ms 9952 KB Output is correct
3 Correct 11 ms 9952 KB Output is correct
4 Correct 13 ms 10072 KB Output is correct
5 Correct 11 ms 10180 KB Output is correct
6 Correct 11 ms 10232 KB Output is correct
7 Incorrect 11 ms 10232 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 129 ms 26708 KB Output is correct
2 Correct 121 ms 28000 KB Output is correct
3 Correct 191 ms 32864 KB Output is correct
4 Correct 181 ms 32864 KB Output is correct
5 Correct 206 ms 32864 KB Output is correct
6 Correct 324 ms 38068 KB Output is correct
7 Correct 289 ms 38068 KB Output is correct
8 Correct 273 ms 38068 KB Output is correct
9 Correct 174 ms 38068 KB Output is correct
10 Correct 255 ms 38068 KB Output is correct
11 Correct 195 ms 38068 KB Output is correct
12 Correct 186 ms 38068 KB Output is correct
13 Correct 111 ms 38068 KB Output is correct
14 Correct 165 ms 38068 KB Output is correct
15 Correct 95 ms 38068 KB Output is correct
16 Correct 90 ms 38068 KB Output is correct
17 Correct 24 ms 38068 KB Output is correct
18 Correct 16 ms 38068 KB Output is correct
19 Correct 17 ms 38068 KB Output is correct
20 Correct 19 ms 38068 KB Output is correct
21 Correct 17 ms 38068 KB Output is correct
22 Correct 16 ms 38068 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 42288 KB Output is correct
2 Correct 340 ms 43404 KB Output is correct
3 Correct 245 ms 44788 KB Output is correct
4 Correct 278 ms 46112 KB Output is correct
5 Correct 214 ms 47280 KB Output is correct
6 Correct 393 ms 68088 KB Output is correct
7 Correct 339 ms 68088 KB Output is correct
8 Correct 318 ms 68088 KB Output is correct
9 Correct 370 ms 68088 KB Output is correct
10 Correct 315 ms 68088 KB Output is correct
11 Correct 276 ms 68088 KB Output is correct
12 Correct 220 ms 68088 KB Output is correct
13 Correct 339 ms 68088 KB Output is correct
14 Correct 230 ms 68088 KB Output is correct
15 Correct 211 ms 68088 KB Output is correct
16 Correct 120 ms 68088 KB Output is correct
17 Correct 119 ms 68088 KB Output is correct
18 Correct 105 ms 68088 KB Output is correct
19 Correct 94 ms 68088 KB Output is correct
20 Correct 101 ms 68088 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 68088 KB Output is correct
2 Correct 13 ms 68088 KB Output is correct
3 Incorrect 16 ms 68088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 68088 KB Output is correct
2 Correct 329 ms 68088 KB Output is correct
3 Runtime error 172 ms 78844 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 12 ms 9848 KB Output is correct
2 Correct 14 ms 9952 KB Output is correct
3 Correct 11 ms 9952 KB Output is correct
4 Correct 13 ms 10072 KB Output is correct
5 Correct 11 ms 10180 KB Output is correct
6 Correct 11 ms 10232 KB Output is correct
7 Incorrect 11 ms 10232 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9848 KB Output is correct
2 Correct 14 ms 9952 KB Output is correct
3 Correct 11 ms 9952 KB Output is correct
4 Correct 13 ms 10072 KB Output is correct
5 Correct 11 ms 10180 KB Output is correct
6 Correct 11 ms 10232 KB Output is correct
7 Incorrect 11 ms 10232 KB Output isn't correct
8 Halted 0 ms 0 KB -