oj.uz

Submission #771783

# Submission time Handle Problem Language Result Execution time Memory
771783 2023-07-03T09:16:51 Z gagik_2007 Duathlon (APIO18_duathlon) C++17
23 / 100
 946 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

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

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
ll n,m,k;
vector<int>g[N];
ll sz[N];

void dfs(int v, int par=-1){
    sz[v]=1;
    for(int to:g[v]){
        if(to!=par){
            dfs(to,v);
            sz[v]+=sz[to];
        }
    }
}

void calc_ans(int c, int v, ll& ans, int par=-1){
    ll sum=0;
    for(int to:g[v]){
        if(to!=par){
            calc_ans(c,to,ans,v);
            ans+=sz[to]*(c-sz[to]-1);
            sum+=sz[to];
        }
    }
    ans+=sum*(c-sum-1);
}

int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    ll ans=0;
    for(int v=1;v<=n;v++){
        if(sz[v]==0){
            dfs(v);
            calc_ans(sz[v],v,ans);
        }
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 424 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 424 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 946 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11492 KB Output is correct
2 Correct 59 ms 12580 KB Output is correct
3 Correct 60 ms 12548 KB Output is correct
4 Correct 58 ms 12544 KB Output is correct
5 Correct 60 ms 12584 KB Output is correct
6 Correct 64 ms 17484 KB Output is correct
7 Correct 79 ms 15860 KB Output is correct
8 Correct 64 ms 14924 KB Output is correct
9 Correct 62 ms 14128 KB Output is correct
10 Correct 58 ms 12492 KB Output is correct
11 Correct 58 ms 12492 KB Output is correct
12 Correct 60 ms 12488 KB Output is correct
13 Correct 63 ms 12616 KB Output is correct
14 Correct 52 ms 12340 KB Output is correct
15 Correct 48 ms 12108 KB Output is correct
16 Correct 31 ms 11088 KB Output is correct
17 Correct 51 ms 12848 KB Output is correct
18 Correct 54 ms 12828 KB Output is correct
19 Correct 51 ms 12864 KB Output is correct
20 Correct 51 ms 12812 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Runtime error 434 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 11348 KB Output is correct
2 Correct 74 ms 11984 KB Output is correct
3 Runtime error 523 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 424 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 424 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -