oj.uz

Submission #567171

# Submission time Handle Problem Language Result Execution time Memory
567171 2022-05-23T08:48:19 Z Mahdi Duathlon (APIO18_duathlon) C++17
23 / 100
 89 ms 18412 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll>pil;
const int N=1e5+5;
int n, m, sz[N], nn;
vector<int>g[N], nd, kd[N];
bool mk[N];

void dfs(const int &v){
    mk[v]=1;
    sz[v]=1;
    nd.push_back(v);
    for(int u: g[v]){
        if(!mk[u]){
            kd[v].push_back(u);
            dfs(u);
            sz[v]+=sz[u];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    if(m>=n)
        return 0;
    for(int i=0;i<m;++i){
        int u, v;
        cin>>u>>v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    ll ans=0;
    for(int i=0;i<n;++i){
        if(!mk[i]){
            dfs(i);
            for(int v: nd){
                nn=nd.size();
                ans+=1LL*(nn-1)*(nn-2);
                ans-=1LL*(nn-sz[v])*(nn-sz[v]-1);
                for(int u: kd[v])
                    ans-=1LL*sz[u]*(sz[u]-1);
            }
            nd.clear();
        }
    }
    cout<<ans<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 11976 KB Output is correct
2 Correct 64 ms 12068 KB Output is correct
3 Correct 79 ms 11928 KB Output is correct
4 Correct 67 ms 11932 KB Output is correct
5 Correct 64 ms 11900 KB Output is correct
6 Correct 70 ms 18412 KB Output is correct
7 Correct 75 ms 16032 KB Output is correct
8 Correct 67 ms 14920 KB Output is correct
9 Correct 89 ms 14036 KB Output is correct
10 Correct 67 ms 11784 KB Output is correct
11 Correct 69 ms 11920 KB Output is correct
12 Correct 61 ms 11736 KB Output is correct
13 Correct 58 ms 11704 KB Output is correct
14 Correct 63 ms 11312 KB Output is correct
15 Correct 52 ms 11116 KB Output is correct
16 Correct 47 ms 9696 KB Output is correct
17 Correct 36 ms 11420 KB Output is correct
18 Correct 36 ms 11376 KB Output is correct
19 Correct 36 ms 11352 KB Output is correct
20 Correct 36 ms 11252 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11920 KB Output is correct
2 Correct 70 ms 12144 KB Output is correct
3 Incorrect 3 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -