oj.uz

Submission #152966

# Submission time Handle Problem Language Result Execution time Memory
152966 2019-09-11T00:21:53 Z arnold518 Duathlon (APIO18_duathlon) C++14
31 / 100
 138 ms 22008 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]*(bsz[now]-1)*2-(ll)sum*(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 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4956 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Incorrect 6 ms 5112 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 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4956 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Incorrect 6 ms 5112 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 85 ms 16696 KB Output is correct
2 Correct 91 ms 16624 KB Output is correct
3 Correct 108 ms 15864 KB Output is correct
4 Correct 84 ms 17012 KB Output is correct
5 Correct 96 ms 15096 KB Output is correct
6 Correct 109 ms 17624 KB Output is correct
7 Correct 98 ms 14968 KB Output is correct
8 Correct 119 ms 16376 KB Output is correct
9 Correct 96 ms 14200 KB Output is correct
10 Correct 98 ms 14456 KB Output is correct
11 Correct 78 ms 12792 KB Output is correct
12 Correct 78 ms 12664 KB Output is correct
13 Correct 72 ms 12648 KB Output is correct
14 Correct 66 ms 12536 KB Output is correct
15 Correct 59 ms 12028 KB Output is correct
16 Correct 57 ms 11896 KB Output is correct
17 Correct 10 ms 6648 KB Output is correct
18 Correct 12 ms 6652 KB Output is correct
19 Correct 12 ms 6648 KB Output is correct
20 Correct 11 ms 6776 KB Output is correct
21 Correct 12 ms 6776 KB Output is correct
22 Correct 11 ms 6776 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 5112 KB Output is correct
4 Correct 7 ms 5172 KB Output is correct
5 Correct 7 ms 5116 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5212 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5084 KB Output is correct
11 Correct 7 ms 5160 KB Output is correct
12 Correct 7 ms 5192 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Correct 7 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 7 ms 5112 KB Output is correct
17 Correct 7 ms 5164 KB Output is correct
18 Correct 7 ms 5112 KB Output is correct
19 Correct 7 ms 5112 KB Output is correct
20 Correct 7 ms 5112 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 13920 KB Output is correct
2 Correct 111 ms 14200 KB Output is correct
3 Correct 138 ms 14200 KB Output is correct
4 Correct 126 ms 14200 KB Output is correct
5 Correct 107 ms 14300 KB Output is correct
6 Correct 120 ms 22008 KB Output is correct
7 Correct 132 ms 16928 KB Output is correct
8 Correct 128 ms 16296 KB Output is correct
9 Correct 117 ms 15480 KB Output is correct
10 Correct 107 ms 14200 KB Output is correct
11 Correct 103 ms 14200 KB Output is correct
12 Correct 108 ms 14200 KB Output is correct
13 Correct 116 ms 14200 KB Output is correct
14 Correct 99 ms 13944 KB Output is correct
15 Correct 104 ms 13604 KB Output is correct
16 Correct 62 ms 12024 KB Output is correct
17 Correct 68 ms 14704 KB Output is correct
18 Correct 71 ms 14728 KB Output is correct
19 Correct 72 ms 15084 KB Output is correct
20 Correct 75 ms 14828 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5116 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 107 ms 13988 KB Output is correct
2 Correct 106 ms 13816 KB Output is correct
3 Incorrect 101 ms 12664 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 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4956 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Incorrect 6 ms 5112 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 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5084 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 6 ms 4956 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Incorrect 6 ms 5112 KB Output isn't correct
8 Halted 0 ms 0 KB -