oj.uz

Submission #159010

# Submission time Handle Problem Language Result Execution time Memory
159010 2019-10-20T05:43:33 Z arnold518 Duathlon (APIO18_duathlon) C++14
31 / 100
 305 ms 38652 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, M;
vector<int> adj[MAXN+10];

int idx[MAXN+10], low[MAXN+10], cnt;
ll ans;

void dfs(int now, int bef)
{
    idx[now]=low[now]=++cnt;
    for(auto nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(!idx[nxt])
        {
            dfs(nxt, now);
            low[now]=min(low[now], low[nxt]);
        }
        else
        {
            low[now]=min(low[now], idx[nxt]);
        }
    }
}

bool vis[MAXN+10];
int sz[MAXN+10];
vector<int> bcc[MAXN+10], adj2[MAXN+10];
int ccnt;

void color(int now, int col)
{
    if(col)
    {
        bcc[now].push_back(col);
        sz[col]++;
    }
    vis[now]=true;

    for(int nxt : adj[now])
    {
        if(vis[nxt]) continue;
        if(idx[now]<=low[nxt])
        {
            ccnt++;
            bcc[now].push_back(ccnt);
            sz[ccnt]++;
            color(nxt, ccnt);
        }
        else
        {
            color(nxt, col);
        }
    }
}

bool vis2[MAXN+10];
void dfs2(int now)
{
    vis2[now]=true;
    for(auto nxt : adj2[now])
    {
        if(vis2[nxt]) continue;
        dfs2(nxt);
        sz[now]+=sz[nxt];
    }
    //printf("!%d %d\n", now, sz[now]);
}

void dfs3(int now, int bef)
{
    ll sum=0, val=0;
    for(int nxt : adj2[now])
    {
        if(nxt==bef) continue;
        sz[now]-=sz[nxt];
        sz[nxt]+=sz[now];
        dfs3(nxt, now);
        sz[nxt]-=sz[now];
        sz[now]+=sz[nxt];
    }
    for(int nxt : adj2[now])
    {
        val-=(ll)sz[nxt]*sz[nxt];
        sum+=sz[nxt];
        //printf("!!!!%d / %d %d\n", now, nxt, sz[nxt]);
    }
    val+=sum*sum;
    //printf("%d %lld %lld\n", now, val, sum);
    if(now>N) ans+=val;
    else ans+=(sz[now]-sum)*val+2*(sz[now]-sum)*((sum-adj2[now].size())*(sz[now]-sum-1)+(sum-adj2[now].size())*(adj2[now].size()-1));//, printf("WOW %d %lld %lld\n", now, (sz[now]-sum)*val, 2*(sz[now]-sum)*((sum-adj2[now].size())*(sz[now]-sum-1)+(sum-adj2[now].size())*(adj2[now].size()-1)));
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(i=1; i<=N; i++)
    {
        if(vis[i]) continue;
        dfs(i, i);
        color(i, 0);
    }
    for(i=1; i<=N; i++)
    {
        if(bcc[i].size()>1)
        {
            for(auto j : bcc[i]) adj2[i+N].push_back(j), adj2[j].push_back(i+N);
            sz[i+N]=1;
        }
    }
    for(i=1; i<=ccnt; i++) ans+=(ll)(sz[i])*(sz[i]-1)*(sz[i]-2); //printf("ANS %lld\n", ans);
    for(i=1; i<=ccnt; i++) sz[i]-=adj2[i].size();
/*
    for(i=1; i<=2*N; i++)
    {
        printf("%d : (%d)", i, sz[i]);
        for(auto j : adj2[i]) printf("%d ", j);
        printf("\n");
    }
*/
    for(i=1; i<=ccnt; i++)
    {
        if(vis2[i]) continue;
        dfs2(i);
        dfs3(i, i);
    }
    printf("%lld", ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:104:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
count_triplets.cpp:106: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:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14460 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Incorrect 14 ms 14456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14460 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Incorrect 14 ms 14456 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 105 ms 29432 KB Output is correct
2 Correct 118 ms 29432 KB Output is correct
3 Correct 164 ms 31836 KB Output is correct
4 Correct 148 ms 30936 KB Output is correct
5 Correct 158 ms 29728 KB Output is correct
6 Correct 187 ms 32292 KB Output is correct
7 Correct 160 ms 30520 KB Output is correct
8 Correct 160 ms 30804 KB Output is correct
9 Correct 161 ms 28988 KB Output is correct
10 Correct 151 ms 28792 KB Output is correct
11 Correct 109 ms 25212 KB Output is correct
12 Correct 109 ms 25092 KB Output is correct
13 Correct 101 ms 24568 KB Output is correct
14 Correct 91 ms 24412 KB Output is correct
15 Correct 75 ms 22520 KB Output is correct
16 Correct 72 ms 22520 KB Output is correct
17 Correct 17 ms 15352 KB Output is correct
18 Correct 17 ms 15352 KB Output is correct
19 Correct 17 ms 15484 KB Output is correct
20 Correct 17 ms 15352 KB Output is correct
21 Correct 16 ms 15352 KB Output is correct
22 Correct 17 ms 15352 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14584 KB Output is correct
2 Correct 15 ms 14612 KB Output is correct
3 Correct 15 ms 14556 KB Output is correct
4 Correct 15 ms 14712 KB Output is correct
5 Correct 15 ms 14684 KB Output is correct
6 Correct 15 ms 14584 KB Output is correct
7 Correct 16 ms 14584 KB Output is correct
8 Correct 16 ms 14584 KB Output is correct
9 Correct 15 ms 14584 KB Output is correct
10 Correct 15 ms 14584 KB Output is correct
11 Correct 15 ms 14584 KB Output is correct
12 Correct 15 ms 14588 KB Output is correct
13 Correct 15 ms 14584 KB Output is correct
14 Correct 15 ms 14584 KB Output is correct
15 Correct 15 ms 14588 KB Output is correct
16 Correct 15 ms 14456 KB Output is correct
17 Correct 15 ms 14508 KB Output is correct
18 Correct 15 ms 14584 KB Output is correct
19 Correct 15 ms 14588 KB Output is correct
20 Correct 15 ms 14584 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 27628 KB Output is correct
2 Correct 164 ms 28880 KB Output is correct
3 Correct 166 ms 28828 KB Output is correct
4 Correct 170 ms 28764 KB Output is correct
5 Correct 169 ms 28820 KB Output is correct
6 Correct 259 ms 38652 KB Output is correct
7 Correct 204 ms 34900 KB Output is correct
8 Correct 229 ms 33368 KB Output is correct
9 Correct 186 ms 31932 KB Output is correct
10 Correct 178 ms 28868 KB Output is correct
11 Correct 185 ms 28944 KB Output is correct
12 Correct 165 ms 28860 KB Output is correct
13 Correct 167 ms 28792 KB Output is correct
14 Correct 146 ms 27896 KB Output is correct
15 Correct 133 ms 27020 KB Output is correct
16 Correct 81 ms 23220 KB Output is correct
17 Correct 97 ms 27772 KB Output is correct
18 Correct 102 ms 27680 KB Output is correct
19 Correct 106 ms 27744 KB Output is correct
20 Correct 94 ms 27768 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 27784 KB Output is correct
2 Correct 225 ms 29204 KB Output is correct
3 Incorrect 305 ms 28408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14460 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Incorrect 14 ms 14456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14460 KB Output is correct
6 Correct 15 ms 14456 KB Output is correct
7 Incorrect 14 ms 14456 KB Output isn't correct
8 Halted 0 ms 0 KB -