oj.uz

Submission #152967

# Submission time Handle Problem Language Result Execution time Memory
152967 2019-09-11T00:24:09 Z arnold518 Duathlon (APIO18_duathlon) C++14
31 / 100
 154 ms 21752 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 = 1e5;
const int MAXM = 2e5;

int N, M;
pii edge[MAXM+10];
vector<int> adj[MAXN+10], adj2[MAXN+10];
ll ans;

int bcc[MAXN+10], bcnt=1, bsz[MAXN+10];
int idx[MAXN+10], cnt=1;
vector<int> S;
int dfs(int now, int bef)
{
    idx[now]=cnt++; S.push_back(now);
    int ret=idx[now];

    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        if(idx[nxt]) ret=min(ret, idx[nxt]);
        else
        {
            int t=dfs(nxt, now);
            ret=min(ret, t);
            if(t>idx[now])
            {
                while(1)
                {
                    int t=S.back(); S.pop_back();
                    bcc[t]=bcnt; bsz[bcnt]++;
                    if(t==nxt) break;
                }
                bcnt++;
            }
        }
    }
    return ret;
}

int sz[MAXN+10];
bool vis[MAXN+10];

void dfs1(int now, int bef)
{
    sz[now]=bsz[now]; vis[now]=true;
    for(int nxt : adj2[now])
    {
        if(nxt==bef) continue;
        dfs1(nxt, now);
        sz[now]+=sz[nxt];
    }
}

void dfs2(int now, int bef)
{
    int sum=0;
    for(int nxt : adj2[now])
    {
        if(nxt==bef) continue;
        sz[now]-=sz[nxt];
        sz[nxt]+=sz[now];
        dfs2(nxt, now);
        sz[nxt]-=sz[now];
        sz[now]+=sz[nxt];
    }
    ll a=0, b=0, c=0;
    a+=(ll)bsz[now]*(bsz[now]-1)*(bsz[now]-2);
    for(int nxt : adj2[now])
    {
        b-=(ll)sz[nxt]*sz[nxt];
        sum+=sz[nxt];
    }
    b+=(ll)sum*sum;
    b*=bsz[now];
    c=(ll)sum*(bsz[now]-1)*(bsz[now]-1)*2;

    ans+=a+b+c;
}

int main()
{
    int i, j;

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

    for(i=1; i<=N; i++) if(idx[i]==0)
    {
        dfs(i, i);
        while(1)
        {
            int t=S.back(); S.pop_back();
            bcc[t]=bcnt; bsz[bcnt]++;
            if(t==i) break;
        }
        bcnt++;
    }
    bcnt--;

    for(i=1; i<=M; i++)
    {
        int u=edge[i].first, v=edge[i].second;
        if(bcc[u]==bcc[v]) continue;
        adj2[bcc[u]].push_back(bcc[v]);
        adj2[bcc[v]].push_back(bcc[u]);
    }

    for(i=1; i<=bcnt; i++)
    {
        sort(adj2[i].begin(), adj2[i].end());
        adj2[i].erase(unique(adj2[i].begin(), adj2[i].end()), adj2[i].end());
    }

    for(i=1; i<=bcnt; i++) if(!vis[i])
    {
        dfs1(i, i);
        dfs2(i, i);
    }
    printf("%lld", ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:89:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
count_triplets.cpp:91: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:95: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 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 7 ms 4984 KB Output is correct
5 Correct 7 ms 5028 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Incorrect 6 ms 4984 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 7 ms 4984 KB Output is correct
5 Correct 7 ms 5028 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Incorrect 6 ms 4984 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 97 ms 16568 KB Output is correct
2 Correct 98 ms 16496 KB Output is correct
3 Correct 108 ms 15860 KB Output is correct
4 Correct 138 ms 15732 KB Output is correct
5 Correct 102 ms 13816 KB Output is correct
6 Correct 111 ms 16376 KB Output is correct
7 Correct 105 ms 13816 KB Output is correct
8 Correct 99 ms 15096 KB Output is correct
9 Correct 140 ms 12968 KB Output is correct
10 Correct 99 ms 13172 KB Output is correct
11 Correct 75 ms 11768 KB Output is correct
12 Correct 79 ms 11768 KB Output is correct
13 Correct 80 ms 11864 KB Output is correct
14 Correct 72 ms 11512 KB Output is correct
15 Correct 56 ms 11384 KB Output is correct
16 Correct 62 ms 11056 KB Output is correct
17 Correct 10 ms 6648 KB Output is correct
18 Correct 10 ms 6648 KB Output is correct
19 Correct 10 ms 6648 KB Output is correct
20 Correct 10 ms 6776 KB Output is correct
21 Correct 10 ms 6668 KB Output is correct
22 Correct 10 ms 6648 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 13984 KB Output is correct
2 Correct 112 ms 14072 KB Output is correct
3 Correct 124 ms 13940 KB Output is correct
4 Correct 106 ms 13948 KB Output is correct
5 Correct 108 ms 13944 KB Output is correct
6 Correct 130 ms 21752 KB Output is correct
7 Correct 115 ms 16760 KB Output is correct
8 Correct 119 ms 16092 KB Output is correct
9 Correct 150 ms 15192 KB Output is correct
10 Correct 154 ms 13916 KB Output is correct
11 Correct 111 ms 13940 KB Output is correct
12 Correct 110 ms 14044 KB Output is correct
13 Correct 113 ms 13980 KB Output is correct
14 Correct 99 ms 13688 KB Output is correct
15 Correct 93 ms 13432 KB Output is correct
16 Correct 66 ms 11768 KB Output is correct
17 Correct 70 ms 14576 KB Output is correct
18 Correct 92 ms 14548 KB Output is correct
19 Correct 77 ms 14824 KB Output is correct
20 Correct 74 ms 14456 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 14016 KB Output is correct
2 Correct 137 ms 13908 KB Output is correct
3 Incorrect 113 ms 12680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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